ref: 7fd74aeb5107b6e0b3f4cfd150fb295a58250d21
parent: 38a875c05a009fdd298e7a93086654c8b78b2f63
author: Ori Bernstein <ori@eigenstate.org>
date: Thu Feb 5 20:03:09 EST 2015
Fix mod.
We weren't adjusting properly all the time.
--- a/libstd/bigint.myr
+++ b/libstd/bigint.myr
@@ -64,7 +64,6 @@
;;
const Base = 0x100000000ul
-
generic mkbigint = {v : @a::(integral,numeric)var a
var val
@@ -445,9 +444,9 @@
/* a /= b */
const bigdivmod = {a : bigint#, b : bigint# -> (bigint#, bigint#)/*
- Implements bigint division using Algorithm D from
- Knuth: Seminumerical algorithms, Section 4.3.1.
- */
+ Implements bigint division using Algorithm D from
+ Knuth: Seminumerical algorithms, Section 4.3.1.
+ */
var m : int64, n : int64
var qhat, rhat, carry, shift
var x, y, z, w, p, t /* temporaries */
@@ -494,6 +493,7 @@
bigshli(u, shift)
bigshli(v, shift)
u.dig = slzgrow(u.dig, u.dig.len + 1)
+
for j = m - n; j >= 0; j--
/* load a few temps */
x = u.dig[j + n] castto(uint64)
@@ -504,7 +504,7 @@
/* estimate qhat */
qhat = (x*Base + y)/z
- rhat = (x*Base + y) - (qhat * z)
+ rhat = (x*Base + y) - qhat*z
:divagain
if qhat >= Base || (qhat * w) > (rhat*Base + t)
qhat--
@@ -518,16 +518,17 @@
carry = 0
for i = 0; i < n; i++
p = qhat * (v.dig[i] castto(uint64))
+
t = (u.dig[i+j] castto(uint64)) - carry - (p % Base)
u.dig[i+j] = t castto(uint32)
+
carry = (((p castto(int64)) >> 32) - ((t castto(int64)) >> 32)) castto(uint64);
;;
- x = u.dig[j + n] castto(uint64)
- t = x - carry
+ t = (u.dig[j + n] castto(uint64)) - carry
u.dig[j + n] = t castto(uint32)
q.dig[j] = qhat castto(uint32)
/* adjust */
- if x < carry
+ if t castto(int64) < 0
q.dig[j]--
carry = 0
for i = 0; i < n; i++
@@ -551,7 +552,7 @@
r = mkbigint(1)
n = 0
while !bigiszero(exp)
- if exp.dig[0] & 1 != 0
+ if (exp.dig[0] & 1) != 0
bigmul(r, base)
bigmod(r, mod)
;;
--- a/test/stdbigint.myr
+++ b/test/stdbigint.myr
@@ -75,13 +75,11 @@
std.mk(`Val "5192296858534810493479828944327220"), \
std.mk(`Val "75557863709417659441940"), \
std.mk(`Val "755578")))))
- /* BOTCHED
run(std.mk(`Res \
std.mk(`Modpow (\
- std.mk(`Val "5192296858534810493479828944327220"), \
+ std.mk(`Val "7220"), \
std.mk(`Val "755578"), \
std.mk(`Val "75557863709417659441940")))))
- */
}