This repository has been archived by the owner on Dec 31, 2024. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 107
/
Copy pathlong_integer_macros.se
116 lines (100 loc) · 2.97 KB
/
long_integer_macros.se
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
macro smin($a, $b):
with $1 = $a:
with $2 = $b:
if(slt($1, $2), $1, $2)
macro smax($a, $b):
with $1 = $a:
with $2 = $b:
if(slt($1, $2), $2, $1)
def omul(x, y):
o = expose(mklong(x) * mklong(y))
return(slice(o, 1), o[0]+1)
def oadd(x, y):
o = expose(mklong(x) + mklong(y))
return(slice(o, 1), o[0]+1)
def osub(x, y):
o = expose(mklong(x) - mklong(y))
return(slice(o, 1), o[0]+1)
def odiv(x, y):
o = expose(mklong(x) / mklong(y))
return(slice(o, 1), o[0]+1)
def comb(a:a, b:a, sign):
sz = smax(a[0], b[0])
msz = smin(a[0], b[0])
c = array(sz + 2)
c[0] = sz
i = 0
carry = 0
while i < msz:
m = a[i + 1] + sign * b[i + 1] + carry
c[i + 1] = mod(m + 2^127, 2^128) - 2^127
carry = (div(m + 2^127, 2^128) + 2^127) % 2^128 - 2^127
i += 1
u = if(a[0] > msz, a, b)
s = if(a[0] > msz, 1, sign)
while i < sz:
m = s * u[i + 1] + carry
c[i + 1] = mod(m + 2^127, 2^128) - 2^127
carry = (div(m + 2^127, 2^128) + 2^127) % 2^128 - 2^127
i += 1
if carry:
c[0] += 1
c[sz + 1] = carry
return(c, c[0]+1)
def mul(a:a, b:a):
c = array(a[0] + b[0] + 2)
c[0] = a[0] + b[0]
i = 0
while i < a[0]:
j = 0
carry = 0
while j < b[0]:
m = c[i + j + 1] + a[i + 1] * b[j + 1] + carry
c[i + j + 1] = mod(m + 2^127, 2^128) - 2^127
carry = (div(m + 2^127, 2^128) + 2^127) % 2^128 - 2^127
j += 1
if carry:
c[0] = a[0] + b[0] + 1
c[i + j + 1] += carry
i += 1
return(c, c[0]+1)
macro long($a) + long($b):
long(self.comb($a:$a[0]+1, $b:$b[0]+1, 1, outsz=$a[0]+$b[0]+2))
macro long($a) - long($b):
long(self.comb($a:$a[0]+1, $b:$b[0]+1, -1, outsz=$a[0]+$b[0]+2))
macro long($a) * long($b):
long(self.mul($a:$a[0]+1, $b:$b[0]+1, outsz=$a[0]+$b[0]+2))
macro long($a) / long($b):
long(self.div($a:$a[0]+1, $b:$b[0]+1, outsz=$a[0]+$b[0]+2))
macro mulexpand(long($a), $k, $m):
long:
with $c = array($a[0]+k+2):
$c[0] = $a[0]+$k
with i = 0:
while i < $a[0]:
v = $a[i+1] * $m + $c[i+$k+1]
$c[i+$k+1] = mod(v + 2^127, 2^128) - 2^127
$c[i+$k+2] = div(v + 2^127, 2^128)
i += 1
$c
def div(a:a, b:a):
asz = a[0]
bsz = b[0]
while b[bsz] == 0 and bsz > 0:
bsz -= 1
c = array(asz+2)
c[0] = asz+1
while 1:
while a[asz] == 0 and asz > 0:
asz -= 1
if asz < bsz:
return(c, c[0]+1)
sub = expose(mulexpand(long(b), asz - bsz, a[asz] / b[bsz]))
c[asz - bsz+1] = a[asz] / b[bsz]
a = expose(long(a) - long(sub))
a[asz-1] += 2^128 * a[asz]
a[asz] = 0
macro mklong($i):
long([2, mod($i + 2^127, 2^128) - 2^127, div($i + 2^127, 2^128)])
macro expose(long($i)):
$i