You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
In order to improve modular exponentiation or to write other higher-order functions (functions that do not rely on BigInts internal representation), we might want to count the number of significant bits (bits after leading zeros, without the sign bit in complement representation of signed integers) or at least the logarithm in base 2 of the number.
We can determine the number of significant bits from the logarithm in base 2 as:
significantBits(n) = floor(log_2(n)) + 1
funcsignificantBits*(n: BigInt): int=if n <0:
returnsignificantBits(-n)
fastLog2(n.limbs.high) +32*(n.limbs.len-1)
How would you optimize the negative case ? Can we just take the two’s complement of the highest limb and then compute the fastLog2(n.limbs.high) ?
funcsignificantBits*(n: BigInt): int=var highest_limb = n.limbs.high
if n <0:
highest_limb =not n.limbs.high +1fastLog2(highest_limb) +32*(n.limbs.len-1)
The text was updated successfully, but these errors were encountered:
I think you're misunderstanding how negative BigInts are stored. Negating a BigInt is just inverting the isNegative flag, nothing is stored in two's complement.
In order to improve modular exponentiation or to write other higher-order functions (functions that do not rely on BigInts internal representation), we might want to count the number of significant bits (bits after leading zeros, without the sign bit in complement representation of signed integers) or at least the logarithm in base 2 of the number.
We can determine the number of significant bits from the logarithm in base 2 as:
significantBits(n) = floor(log_2(n)) + 1
How would you optimize the negative case ? Can we just take the two’s complement of the highest limb and then compute the fastLog2(n.limbs.high) ?
The text was updated successfully, but these errors were encountered: