equal
deleted
inserted
replaced
2063 t *= 2 - val*t; |
2063 t *= 2 - val*t; |
2064 return t; |
2064 return t; |
2065 } |
2065 } |
2066 |
2066 |
2067 /** |
2067 /** |
|
2068 * Returns the multiplicative inverse of val mod 2^64. Assumes val is odd. |
|
2069 */ |
|
2070 static long inverseMod64(long val) { |
|
2071 // Newton's iteration! |
|
2072 long t = val; |
|
2073 t *= 2 - val*t; |
|
2074 t *= 2 - val*t; |
|
2075 t *= 2 - val*t; |
|
2076 t *= 2 - val*t; |
|
2077 t *= 2 - val*t; |
|
2078 assert(t * val == 1); |
|
2079 return t; |
|
2080 } |
|
2081 |
|
2082 /** |
2068 * Calculate the multiplicative inverse of 2^k mod mod, where mod is odd. |
2083 * Calculate the multiplicative inverse of 2^k mod mod, where mod is odd. |
2069 */ |
2084 */ |
2070 static MutableBigInteger modInverseBP2(MutableBigInteger mod, int k) { |
2085 static MutableBigInteger modInverseBP2(MutableBigInteger mod, int k) { |
2071 // Copy the mod to protect original |
2086 // Copy the mod to protect original |
2072 return fixup(new MutableBigInteger(1), new MutableBigInteger(mod), k); |
2087 return fixup(new MutableBigInteger(1), new MutableBigInteger(mod), k); |