finding the best algorithm
-
For the very large number like 2^2000 how do I calculate its value?
-
For the very large number like 2^2000 how do I calculate its value?
Use logarithms.
"Microsoft -- Adding unnecessary complexity to your work since 1987!"
-
Use logarithms.
"Microsoft -- Adding unnecessary complexity to your work since 1987!"
Thank you very much.
-
For the very large number like 2^2000 how do I calculate its value?
Use binary: 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000b
-
For the very large number like 2^2000 how do I calculate its value?
More seriously, an easy option is to work in base 1 billion, using an array of integers. Every integer will store 9 significant decimal digits. It is a rather straightforward matter to implement a doubling algorithm, by means of long addition, as in the following quick Python code.
N= [0] * (Digits - 1) + [1] # Large number representation of 1
for Exponent in range(2000): # Double 2000 times
for Position in range(Digits): # For all digits
N[Position]= 2 * N[Position] # Double this digit
if N[Position] >= Base: # Detect carry out
N[Position]-= Base # Adjust the digit...
N[Position - 1]+= 1 # ... and carry out to the left one
print NOutput:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 114813069, 527425452, 423283320, 117768198, 402231770, 208869520, 47764273, 682576626, 139237031, 385665948, 631650626, 991844596, 463898746, 277344711, 896086305, 533142593, 135616665, 318539129, 989145312, 280000688, 779148240, 44871428, 926990063, 486244781, 615463646, 388363947, 317026040, 466353970, 904996558, 162398808, 944629605, 623311649, 536164221, 970332681, 344168908, 984458505, 602379484, 807914058, 900934776, 500429002, 716706625, 830522008, 132236281, 291761267, 883317206, 598995396, 418127021, 779858404, 42159853, 183251540, 889433902, 91920554, 957783589, 672039160, 81957216, 630582755, 380425583, 726015528, 348786419, 432054508, 915275783, 882625175, 435528800, 822842770, 817965453, 762184851, 149029376]
In reality, this algorithm uses a trick: a carry-in to a digit (from the right) will never cause a carry-out (to the left). This is because the doubled digits are even, at most 999999998, and can stand one incrementation. This allows us to process left-to-right. This property doesn't hold for plain addition where carries can propagate further. A more efficient but a little more complex solution can be achieved by using a base conversion algorithm.
-
Use logarithms.
"Microsoft -- Adding unnecessary complexity to your work since 1987!"
To elaborate on Alan's suggestion... Let's take a big power of 2, such as: 2 ^ 2000 We first re-express it using a power of 10: 10 ^ (2000 * log10 (2)) Which yields: 10 ^ 602.05999132796239042747778944899 But we want it re-expressed in the more useful form of: man * 10^exp, the scientific notation (just in case). We know that x^(a+b) == (x^a) * (x^b), where x=10 and (conveniently) a and b can be the integer and the fractional parts of 602.05999132796239042747778944899 In other words: 10 ^ (602 + 0.05999132796239042747778944899) == (10 ^ 602) * (10 ^ 0.05999132796239042747778944899) We can rearrange it in: 10 ^ 0.05999132796239042747778944899 * 10 ^ 602 Which yields: 1.1481306952742545242328332011881 * 10 ^ 602 And that's the result of 2 ^ 2000: 1.1481306952742545242328332011881e+602 You may calculate this with fixed math, but you won't get as many ULPs and it'll take more time. Either way you're going to get an approximation of the sought value. The above also works with smaller powers. A quick demonstration for: 5^3 = 125 Here: 5^3 = 10 ^ (3 * log10 (5)) 5^3 = 10 ^ 2.0969100130080564143587833158265 5^3 = 10 ^ (2 + 0.0969100130080564143587833158265) 5^3 = (10 ^ 2) * (10 ^ 0.0969100130080564143587833158265) 5^3 = 10 ^ 0.0969100130080564143587833158265 * 10 ^ 2 5^3 = 1.2499999999999999999999999999985 * 10 ^ 2 5^3 = 1.2499999999999999999999999999985e+2 If we account for the rounding error it becomes familiar: 5^3 = 1.25e+2 5^3 = 125 [edited to improve explanation]
-
To elaborate on Alan's suggestion... Let's take a big power of 2, such as: 2 ^ 2000 We first re-express it using a power of 10: 10 ^ (2000 * log10 (2)) Which yields: 10 ^ 602.05999132796239042747778944899 But we want it re-expressed in the more useful form of: man * 10^exp, the scientific notation (just in case). We know that x^(a+b) == (x^a) * (x^b), where x=10 and (conveniently) a and b can be the integer and the fractional parts of 602.05999132796239042747778944899 In other words: 10 ^ (602 + 0.05999132796239042747778944899) == (10 ^ 602) * (10 ^ 0.05999132796239042747778944899) We can rearrange it in: 10 ^ 0.05999132796239042747778944899 * 10 ^ 602 Which yields: 1.1481306952742545242328332011881 * 10 ^ 602 And that's the result of 2 ^ 2000: 1.1481306952742545242328332011881e+602 You may calculate this with fixed math, but you won't get as many ULPs and it'll take more time. Either way you're going to get an approximation of the sought value. The above also works with smaller powers. A quick demonstration for: 5^3 = 125 Here: 5^3 = 10 ^ (3 * log10 (5)) 5^3 = 10 ^ 2.0969100130080564143587833158265 5^3 = 10 ^ (2 + 0.0969100130080564143587833158265) 5^3 = (10 ^ 2) * (10 ^ 0.0969100130080564143587833158265) 5^3 = 10 ^ 0.0969100130080564143587833158265 * 10 ^ 2 5^3 = 1.2499999999999999999999999999985 * 10 ^ 2 5^3 = 1.2499999999999999999999999999985e+2 If we account for the rounding error it becomes familiar: 5^3 = 1.25e+2 5^3 = 125 [edited to improve explanation]
my friend you can use the big integer class it helps you a lot to do such things.
-
More seriously, an easy option is to work in base 1 billion, using an array of integers. Every integer will store 9 significant decimal digits. It is a rather straightforward matter to implement a doubling algorithm, by means of long addition, as in the following quick Python code.
N= [0] * (Digits - 1) + [1] # Large number representation of 1
for Exponent in range(2000): # Double 2000 times
for Position in range(Digits): # For all digits
N[Position]= 2 * N[Position] # Double this digit
if N[Position] >= Base: # Detect carry out
N[Position]-= Base # Adjust the digit...
N[Position - 1]+= 1 # ... and carry out to the left one
print NOutput:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 114813069, 527425452, 423283320, 117768198, 402231770, 208869520, 47764273, 682576626, 139237031, 385665948, 631650626, 991844596, 463898746, 277344711, 896086305, 533142593, 135616665, 318539129, 989145312, 280000688, 779148240, 44871428, 926990063, 486244781, 615463646, 388363947, 317026040, 466353970, 904996558, 162398808, 944629605, 623311649, 536164221, 970332681, 344168908, 984458505, 602379484, 807914058, 900934776, 500429002, 716706625, 830522008, 132236281, 291761267, 883317206, 598995396, 418127021, 779858404, 42159853, 183251540, 889433902, 91920554, 957783589, 672039160, 81957216, 630582755, 380425583, 726015528, 348786419, 432054508, 915275783, 882625175, 435528800, 822842770, 817965453, 762184851, 149029376]
In reality, this algorithm uses a trick: a carry-in to a digit (from the right) will never cause a carry-out (to the left). This is because the doubled digits are even, at most 999999998, and can stand one incrementation. This allows us to process left-to-right. This property doesn't hold for plain addition where carries can propagate further. A more efficient but a little more complex solution can be achieved by using a base conversion algorithm.
There is actually a subtle bug in your code. If, on the last pass of your outer loop, one "digit" is == Base - 1 and you carry into it, you never get to carry out of it. If you write your inner loop backwards (or reverse your array), it all comes out in the wash... The point is that multiprecision add/subtract should be done "right to left" so multiplace carry propagation can occur naturally. A small point, but still important. The one time it bit me, the code was in ROM inside tamper-proof enclosures. A real PITA to fix... Cheers, Peter
Software rusts. Simon Stephenson, ca 1994. So does this signature. me, 2012
-
There is actually a subtle bug in your code. If, on the last pass of your outer loop, one "digit" is == Base - 1 and you carry into it, you never get to carry out of it. If you write your inner loop backwards (or reverse your array), it all comes out in the wash... The point is that multiprecision add/subtract should be done "right to left" so multiplace carry propagation can occur naturally. A small point, but still important. The one time it bit me, the code was in ROM inside tamper-proof enclosures. A real PITA to fix... Cheers, Peter
Software rusts. Simon Stephenson, ca 1994. So does this signature. me, 2012
You are quite right, sorry for having mislead you. This is the kind of "off by one" trap I too easily fall into. When I wrote this code I was indeed unsure in what way to go, and I just satisfied myself when I saw successful tests. There is indeed no carry propagation here and this could have been avoided by careful proofreading: when the carry is made, it applies to digit
Position-1, showing that propagation needs to be done by decreasing indexes. Mea culpa. How did you discover the flaw ? -
There is actually a subtle bug in your code. If, on the last pass of your outer loop, one "digit" is == Base - 1 and you carry into it, you never get to carry out of it. If you write your inner loop backwards (or reverse your array), it all comes out in the wash... The point is that multiprecision add/subtract should be done "right to left" so multiplace carry propagation can occur naturally. A small point, but still important. The one time it bit me, the code was in ROM inside tamper-proof enclosures. A real PITA to fix... Cheers, Peter
Software rusts. Simon Stephenson, ca 1994. So does this signature. me, 2012
The reason why I processed left to right is that the carry needs to be done after the doubling of the digit to the left.
-
You are quite right, sorry for having mislead you. This is the kind of "off by one" trap I too easily fall into. When I wrote this code I was indeed unsure in what way to go, and I just satisfied myself when I saw successful tests. There is indeed no carry propagation here and this could have been avoided by careful proofreading: when the carry is made, it applies to digit
Position-1, showing that propagation needs to be done by decreasing indexes. Mea culpa. How did you discover the flaw ?YvesDaoust wrote:
How did you discover the flaw ?
In my case, we were doing 32 bit arithmetic on an 8-bit processor. The little machine was attached to the memory system of its larger host, reading messages from there, processing them (cryptographically) and writing the results back. A nasty combination of buffer size and alignment meant that occasionally a block would be read from the wrong place, or, worse, written to the wrong place. Three of us spent a good week staring at code, running simulations and generally not seeing what was under our noses. In the 30-odd years since, I have been sensitised to that kind of bug. Cheers, Peter
Software rusts. Simon Stephenson, ca 1994. So does this signature. me, 2012
-
YvesDaoust wrote:
How did you discover the flaw ?
In my case, we were doing 32 bit arithmetic on an 8-bit processor. The little machine was attached to the memory system of its larger host, reading messages from there, processing them (cryptographically) and writing the results back. A nasty combination of buffer size and alignment meant that occasionally a block would be read from the wrong place, or, worse, written to the wrong place. Three of us spent a good week staring at code, running simulations and generally not seeing what was under our noses. In the 30-odd years since, I have been sensitised to that kind of bug. Cheers, Peter
Software rusts. Simon Stephenson, ca 1994. So does this signature. me, 2012
Interesting. Given that you work with an 8 bits processor, base 100 could have been an option too. But now I am getting quite puzzled as I believe that multiple carries are not possible: when you double a digit, this can cause a carry-out; in all cases you get an even digit, at most Base-2; for the same digit, the carry-in cannot cause an extra carry-out. Said differently, the doubling of digits generates all the carries-out it needs to, and my original algorithm is correct. On the opposite, merely reversing the traversal direction causes all carries-out to be unduly doubled.