arithmetic.gno
8.40 Kb ยท 350 lines
1package int256
2
3import (
4 "gno.land/p/demo/uint256"
5)
6
7const divisionByZeroError = "division by zero"
8
9// Add adds two int256 values and saves the result in z.
10func (z *Int) Add(x, y *Int) *Int {
11 z.value.Add(&x.value, &y.value)
12 return z
13}
14
15// AddUint256 adds int256 and uint256 values and saves the result in z.
16func (z *Int) AddUint256(x *Int, y *uint256.Uint) *Int {
17 z.value.Add(&x.value, y)
18 return z
19}
20
21// Sub subtracts two int256 values and saves the result in z.
22func (z *Int) Sub(x, y *Int) *Int {
23 z.value.Sub(&x.value, &y.value)
24 return z
25}
26
27// SubUint256 subtracts uint256 and int256 values and saves the result in z.
28func (z *Int) SubUint256(x *Int, y *uint256.Uint) *Int {
29 z.value.Sub(&x.value, y)
30 return z
31}
32
33// Mul multiplies two int256 values and saves the result in z.
34//
35// It considers the signs of the operands to determine the sign of the result.
36func (z *Int) Mul(x, y *Int) *Int {
37 xAbs, xSign := x.Abs(), x.Sign()
38 yAbs, ySign := y.Abs(), y.Sign()
39
40 z.value.Mul(xAbs, yAbs)
41
42 if xSign != ySign {
43 z.value.Neg(&z.value)
44 }
45
46 return z
47}
48
49// Abs returns the absolute value of z.
50func (z *Int) Abs() *uint256.Uint {
51 if z.Sign() >= 0 {
52 return &z.value
53 }
54
55 var absValue uint256.Uint
56 absValue.Sub(uint0, &z.value).Neg(&z.value)
57
58 return &absValue
59}
60
61// Div performs integer division z = x / y and returns z.
62// If y == 0, it panics with a "division by zero" error.
63//
64// This function handles signed division using two's complement representation:
65// 1. Determine the sign of the quotient based on the signs of x and y.
66// 2. Perform unsigned division on the absolute values.
67// 3. Adjust the result's sign if necessary.
68//
69// Example visualization for 8-bit integers (scaled down from 256-bit for simplicity):
70//
71// Let x = -6 (11111010 in two's complement) and y = 3 (00000011)
72//
73// Step 2: Determine signs
74//
75// x: negative (MSB is 1)
76// y: positive (MSB is 0)
77//
78// Step 3: Calculate absolute values
79//
80// |x| = 6: 11111010 -> 00000110
81// NOT: 00000101
82// +1: 00000110
83//
84// |y| = 3: 00000011 (already positive)
85//
86// Step 4: Unsigned division
87//
88// 6 / 3 = 2: 00000010
89//
90// Step 5: Adjust sign (x and y have different signs)
91//
92// -2: 00000010 -> 11111110
93// NOT: 11111101
94// +1: 11111110
95//
96// Note: This implementation rounds towards zero, as is standard in Go.
97func (z *Int) Div(x, y *Int) *Int {
98 // Step 1: Check for division by zero
99 if y.IsZero() {
100 panic(divisionByZeroError)
101 }
102
103 // Step 2, 3: Calculate the absolute values of x and y
104 xAbs, xSign := x.Abs(), x.Sign()
105 yAbs, ySign := y.Abs(), y.Sign()
106
107 // Step 4: Perform unsigned division on the absolute values
108 z.value.Div(xAbs, yAbs)
109
110 // Step 5: Adjust the sign of the result
111 // if x and y have different signs, the result must be negative
112 if xSign != ySign {
113 z.value.Neg(&z.value)
114 }
115
116 return z
117}
118
119// Example visualization for 8-bit integers (scaled down from 256-bit for simplicity):
120//
121// Let x = -7 (11111001 in two's complement) and y = 3 (00000011)
122//
123// Step 2: Determine signs
124//
125// x: negative (MSB is 1)
126// y: positive (MSB is 0)
127//
128// Step 3: Calculate absolute values
129//
130// |x| = 7: 11111001 -> 00000111
131// NOT: 00000110
132// +1: 00000111
133//
134// |y| = 3: 00000011 (already positive)
135//
136// Step 4: Unsigned division
137//
138// 7 / 3 = 2: 00000010
139//
140// Step 5: Adjust sign (x and y have different signs)
141//
142// -2: 00000010 -> 11111110
143// NOT: 11111101
144// +1: 11111110
145//
146// Final result: -2 (11111110 in two's complement)
147//
148// Note: This implementation rounds towards zero, as is standard in Go.
149func (z *Int) Quo(x, y *Int) *Int {
150 // Step 1: Check for division by zero
151 if y.IsZero() {
152 panic(divisionByZeroError)
153 }
154
155 // Step 2, 3: Calculate the absolute values of x and y
156 xAbs, xSign := x.Abs(), x.Sign()
157 yAbs, ySign := y.Abs(), y.Sign()
158
159 // perform unsigned division on the absolute values
160 z.value.Div(xAbs, yAbs)
161
162 // Step 5: Adjust the sign of the result
163 // if x and y have different signs, the result must be negative
164 if xSign != ySign {
165 z.value.Neg(&z.value)
166 }
167
168 return z
169}
170
171// Rem sets z to the remainder x%y for y != 0 and returns z.
172//
173// The function performs the following steps:
174// 1. Check for division by zero
175// 2. Determine the signs of x and y
176// 3. Calculate the absolute values of x and y
177// 4. Perform unsigned division and get the remainder
178// 5. Adjust the sign of the remainder
179//
180// Example visualization for 8-bit integers (scaled down from 256-bit for simplicity):
181//
182// Let x = -7 (11111001 in two's complement) and y = 3 (00000011)
183//
184// Step 2: Determine signs
185//
186// x: negative (MSB is 1)
187// y: positive (MSB is 0)
188//
189// Step 3: Calculate absolute values
190//
191// |x| = 7: 11111001 -> 00000111
192// NOT: 00000110
193// +1: 00000111
194//
195// |y| = 3: 00000011 (already positive)
196//
197// Step 4: Unsigned division
198//
199// 7 / 3 = 2 remainder 1
200// q = 2: 00000010 (not used in result)
201// r = 1: 00000001
202//
203// Step 5: Adjust sign of remainder (x is negative)
204//
205// -1: 00000001 -> 11111111
206// NOT: 11111110
207// +1: 11111111
208//
209// Final result: -1 (11111111 in two's complement)
210//
211// Note: The sign of the remainder is always the same as the sign of the dividend (x).
212func (z *Int) Rem(x, y *Int) *Int {
213 // Step 1: Check for division by zero
214 if y.IsZero() {
215 panic(divisionByZeroError)
216 }
217
218 // Step 2, 3
219 xAbs, xSign := x.Abs(), x.Sign()
220 yAbs := y.Abs()
221
222 // Step 4: Perform unsigned division and get the remainder
223 var q, r uint256.Uint
224 q.DivMod(xAbs, yAbs, &r)
225
226 // Step 5: Adjust the sign of the remainder
227 if xSign < 0 {
228 r.Neg(&r)
229 }
230
231 z.value.Set(&r)
232 return z
233}
234
235// Mod sets z to the modulus x%y for y != 0 and returns z.
236// The result (z) has the same sign as the divisor y.
237func (z *Int) Mod(x, y *Int) *Int {
238 return z.ModE(x, y)
239}
240
241// DivE performs Euclidean division of x by y, setting z to the quotient and returning z.
242// If y == 0, it panics with a "division by zero" error.
243//
244// Euclidean division satisfies the following properties:
245// 1. The remainder is always non-negative: 0 <= x mod y < |y|
246// 2. It follows the identity: x = y * (x div y) + (x mod y)
247func (z *Int) DivE(x, y *Int) *Int {
248 if y.IsZero() {
249 panic(divisionByZeroError)
250 }
251
252 // Compute the truncated division quotient
253 z.Quo(x, y)
254
255 // Compute the remainder
256 r := new(Int).Rem(x, y)
257
258 // If the remainder is negative, adjust the quotient
259 if r.Sign() < 0 {
260 if y.Sign() > 0 {
261 z.Sub(z, NewInt(1))
262 } else {
263 z.Add(z, NewInt(1))
264 }
265 }
266
267 return z
268}
269
270// ModE computes the Euclidean modulus of x by y, setting z to the result and returning z.
271// If y == 0, it panics with a "division by zero" error.
272//
273// The Euclidean modulus is always non-negative and satisfies:
274//
275// 0 <= x mod y < |y|
276//
277// Example visualization for 8-bit integers (scaled down from 256-bit for simplicity):
278//
279// Case 1: Let x = -7 (11111001 in two's complement) and y = 3 (00000011)
280//
281// Step 1: Compute remainder (using Rem)
282//
283// Result of Rem: -1 (11111111 in two's complement)
284//
285// Step 2: Adjust sign (result is negative, y is positive)
286//
287// -1 + 3 = 2
288// 11111111 + 00000011 = 00000010
289//
290// Final result: 2 (00000010)
291//
292// Case 2: Let x = -7 (11111001 in two's complement) and y = -3 (11111101 in two's complement)
293//
294// Step 1: Compute remainder (using Rem)
295//
296// Result of Rem: -1 (11111111 in two's complement)
297//
298// Step 2: Adjust sign (result is negative, y is negative)
299//
300// No adjustment needed
301//
302// Final result: -1 (11111111 in two's complement)
303//
304// Note: This implementation ensures that the result always has the same sign as y,
305// which is different from the Rem operation.
306func (z *Int) ModE(x, y *Int) *Int {
307 if y.IsZero() {
308 panic(divisionByZeroError)
309 }
310
311 // Perform T-division to get the remainder
312 z.Rem(x, y)
313
314 // Adjust the remainder if necessary
315 if z.Sign() >= 0 {
316 return z
317 }
318 if y.Sign() > 0 {
319 return z.Add(z, y)
320 }
321
322 return z.Sub(z, y)
323}
324
325// Sets z to the sum x + y, where z and x are uint256s and y is an int256.
326//
327// If the y is positive, it adds y.value to x. otherwise, it subtracts y.Abs() from x.
328func AddDelta(z, x *uint256.Uint, y *Int) {
329 if y.Sign() >= 0 {
330 z.Add(x, &y.value)
331 } else {
332 z.Sub(x, y.Abs())
333 }
334}
335
336// Sets z to the sum x + y, where z and x are uint256s and y is an int256.
337//
338// This function returns true if the addition overflows, false otherwise.
339func AddDeltaOverflow(z, x *uint256.Uint, y *Int) bool {
340 var overflow bool
341 if y.Sign() >= 0 {
342 _, overflow = z.AddOverflow(x, &y.value)
343 } else {
344 var absY uint256.Uint
345 absY.Sub(uint0, &y.value) // absY = -y.value
346 _, overflow = z.SubOverflow(x, &absY)
347 }
348
349 return overflow
350}
