Mutliplying a very long number
-
I tried much in this, but I couldn't get to any thing. I want to get 21000 and put it in an integer, when I put it in a double it give something like 1.80934987391E+301, I want all the 302 digits, so I tried parsing in a string but it parses the same thing, I heard that something like this can be done by catching the overrun exception, but I really can't do it. :^) Can any one help ?
-
I tried much in this, but I couldn't get to any thing. I want to get 21000 and put it in an integer, when I put it in a double it give something like 1.80934987391E+301, I want all the 302 digits, so I tried parsing in a string but it parses the same thing, I heard that something like this can be done by catching the overrun exception, but I really can't do it. :^) Can any one help ?
Hi, 2^1000 has more than 300 decimal digits, obviously it wont fit in an int or a long. 2^1000 = 10,715,086,071,862,673,209,484,250,490,600,018,105,614,048,117, 055,336,074,437,503,883,703,510,511,249,361,224,931,983,788, 156,958,581,275,946,729,175,531,468,251,871,452,856,923,140, 435,984,577,574,698,574,803,934,567,774,824,230,985,421,074, 605,062,371,141,877,954,182,153,046,474,983,581,941,267,398, 767,559,165,543,946,077,062,914,571,196,477,686,542,167,660, 429,831,652,624,386,837,205,668,069,376 (302 digits) there are basically three ways to get all the digits: 1. use very clever code, based on mathematics, to calculate one or a few digits at a time, without ever holding them all. Hint: the last digit can easily be predicted, the powers of two end on 2/4/8/6/2/4/8/6/... 2. use a library that can handle "big integers"; there are some on CP, and many more on Google. Only a very small part of such a lib is actually needed here, since 2^1000 simply gets represented as a 1 followed by a thousand zeroes in binary. So the one thing that remains to be done is the ToString() of that... 3. cheat and go to http://www.newdream.net/~sage/old/numbers/pow2.htm[^] :)
Luc Pattyn [My Articles]
-
Hi, 2^1000 has more than 300 decimal digits, obviously it wont fit in an int or a long. 2^1000 = 10,715,086,071,862,673,209,484,250,490,600,018,105,614,048,117, 055,336,074,437,503,883,703,510,511,249,361,224,931,983,788, 156,958,581,275,946,729,175,531,468,251,871,452,856,923,140, 435,984,577,574,698,574,803,934,567,774,824,230,985,421,074, 605,062,371,141,877,954,182,153,046,474,983,581,941,267,398, 767,559,165,543,946,077,062,914,571,196,477,686,542,167,660, 429,831,652,624,386,837,205,668,069,376 (302 digits) there are basically three ways to get all the digits: 1. use very clever code, based on mathematics, to calculate one or a few digits at a time, without ever holding them all. Hint: the last digit can easily be predicted, the powers of two end on 2/4/8/6/2/4/8/6/... 2. use a library that can handle "big integers"; there are some on CP, and many more on Google. Only a very small part of such a lib is actually needed here, since 2^1000 simply gets represented as a 1 followed by a thousand zeroes in binary. So the one thing that remains to be done is the ToString() of that... 3. cheat and go to http://www.newdream.net/~sage/old/numbers/pow2.htm[^] :)
Luc Pattyn [My Articles]
Luc Pattyn wrote:
2^1000 = 10,715,086,071,862,673,209,484,250,490,600,018,105,614,048,117, 055,336,074,437,503,883,703,510,511,249,361,224,931,983,788, 156,958,581,275,946,729,175,531,468,251,871,452,856,923,140, 435,984,577,574,698,574,803,934,567,774,824,230,985,421,074, 605,062,371,141,877,954,182,153,046,474,983,581,941,267,398, 767,559,165,543,946,077,062,914,571,196,477,686,542,167,660, 429,831,652,624,386,837,205,668,069,376
Can you please tell how do you calculate such a big number?
Regards, Arun Kumar.A
-
Luc Pattyn wrote:
2^1000 = 10,715,086,071,862,673,209,484,250,490,600,018,105,614,048,117, 055,336,074,437,503,883,703,510,511,249,361,224,931,983,788, 156,958,581,275,946,729,175,531,468,251,871,452,856,923,140, 435,984,577,574,698,574,803,934,567,774,824,230,985,421,074, 605,062,371,141,877,954,182,153,046,474,983,581,941,267,398, 767,559,165,543,946,077,062,914,571,196,477,686,542,167,660, 429,831,652,624,386,837,205,668,069,376
Can you please tell how do you calculate such a big number?
Regards, Arun Kumar.A
I don't know how Luc did it, but using any large integer library will allow you to do it. Some languages support large integers, e.g. in Python (free), typing pow(2,1000) gives:
>>> pow(2,1000) 1071508607186267320948425049060001810561404811705533607443750388370351051124936122493198378815695858 1275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954 1821530464749835819412673987675591655439460770629145711964776865421676604298316526243868372056680693 76LI know that mathematica also supports large integers. To do it in say c++, you need to write code, or use a large integer library - type large integer into the search box at the top of the page. If you are asking how it is done, simply by using long multiplication / division. If the native int representation is 32 bits, then to represent a 1001 bit number needs 32 ints. You can write routines to do standard +,=,* and / operations on these numbers, it is much the same as in base 10 - you need to worry about carrying and borrowing. It is not that hard - I did it some years ago when I wrote some crypto routines (one of the major uses for large integer libraries these days), but libraries are readily available these days. Long division is the tricky one - I confess to resorting to Donald Knuth's book to get my algorithm right. To work out 2^1000 is simply a number with 1 followed by 1000 '0's as Luc noted, the decimal representation is probably worked out using long division.
Peter "Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
-
I don't know how Luc did it, but using any large integer library will allow you to do it. Some languages support large integers, e.g. in Python (free), typing pow(2,1000) gives:
>>> pow(2,1000) 1071508607186267320948425049060001810561404811705533607443750388370351051124936122493198378815695858 1275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954 1821530464749835819412673987675591655439460770629145711964776865421676604298316526243868372056680693 76LI know that mathematica also supports large integers. To do it in say c++, you need to write code, or use a large integer library - type large integer into the search box at the top of the page. If you are asking how it is done, simply by using long multiplication / division. If the native int representation is 32 bits, then to represent a 1001 bit number needs 32 ints. You can write routines to do standard +,=,* and / operations on these numbers, it is much the same as in base 10 - you need to worry about carrying and borrowing. It is not that hard - I did it some years ago when I wrote some crypto routines (one of the major uses for large integer libraries these days), but libraries are readily available these days. Long division is the tricky one - I confess to resorting to Donald Knuth's book to get my algorithm right. To work out 2^1000 is simply a number with 1 followed by 1000 '0's as Luc noted, the decimal representation is probably worked out using long division.
Peter "Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
Thank you very much..:):):)
Regards, Arun Kumar.A
-
Luc Pattyn wrote:
2^1000 = 10,715,086,071,862,673,209,484,250,490,600,018,105,614,048,117, 055,336,074,437,503,883,703,510,511,249,361,224,931,983,788, 156,958,581,275,946,729,175,531,468,251,871,452,856,923,140, 435,984,577,574,698,574,803,934,567,774,824,230,985,421,074, 605,062,371,141,877,954,182,153,046,474,983,581,941,267,398, 767,559,165,543,946,077,062,914,571,196,477,686,542,167,660, 429,831,652,624,386,837,205,668,069,376
Can you please tell how do you calculate such a big number?
Regards, Arun Kumar.A
-
Hi, 2^1000 has more than 300 decimal digits, obviously it wont fit in an int or a long. 2^1000 = 10,715,086,071,862,673,209,484,250,490,600,018,105,614,048,117, 055,336,074,437,503,883,703,510,511,249,361,224,931,983,788, 156,958,581,275,946,729,175,531,468,251,871,452,856,923,140, 435,984,577,574,698,574,803,934,567,774,824,230,985,421,074, 605,062,371,141,877,954,182,153,046,474,983,581,941,267,398, 767,559,165,543,946,077,062,914,571,196,477,686,542,167,660, 429,831,652,624,386,837,205,668,069,376 (302 digits) there are basically three ways to get all the digits: 1. use very clever code, based on mathematics, to calculate one or a few digits at a time, without ever holding them all. Hint: the last digit can easily be predicted, the powers of two end on 2/4/8/6/2/4/8/6/... 2. use a library that can handle "big integers"; there are some on CP, and many more on Google. Only a very small part of such a lib is actually needed here, since 2^1000 simply gets represented as a 1 followed by a thousand zeroes in binary. So the one thing that remains to be done is the ToString() of that... 3. cheat and go to http://www.newdream.net/~sage/old/numbers/pow2.htm[^] :)
Luc Pattyn [My Articles]
-
I tried much in this, but I couldn't get to any thing. I want to get 21000 and put it in an integer, when I put it in a double it give something like 1.80934987391E+301, I want all the 302 digits, so I tried parsing in a string but it parses the same thing, I heard that something like this can be done by catching the overrun exception, but I really can't do it. :^) Can any one help ?