20081127, 20:20  #1 
May 2007
3 Posts 
Big integer speed in bases.
I'm curious on how the large integer arithmetic is usually implemented in programs. I know that the numbers are in the linked list. So for example if I want to multiply 123454452544545 by 543490553480954 then I have might have an element 545 in a list and 954 in another list. Then I multiply those numbers to get 519930, move 930 to the result list element and add carry.
I was thinking whether this is faster than transform those huge numbers to their binary representation, do multiplication in base 2 and transform the result to base 10. I know that in computers those numbers are already represented by bits but its representation depends on how the linked list has been built. So, which is faster method to do the program that asks the user two big numbers in base 10 and outputs their product in base 10? 
20081127, 20:35  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2×3×1,657 Posts 
Google and wikipedia are your friends.
Just read this  http://en.wikipedia.org/wiki/Multiplication_algorithm The serious algorithms (like those for GIMPS) are outlined in the end 
20081128, 03:30  #3  
"Bob Silverman"
Nov 2003
North of Boston
2·3·29·43 Posts 
Quote:
Run, don't walk, and get yourself a copy of The Art of Computer Programming, Vol II. Read it. It will tell you everything you need or want to know. Multiprecision arithmetic is done internally using a radix that is a power of 2, (the power depends mostly on the word size). Conversion to base 10 happens very infrequently; almost always ONLY at input or output time. 

20081128, 03:32  #4  
"Bob Silverman"
Nov 2003
North of Boston
2·3·29·43 Posts 
Quote:
Such details are important in this application. Read Knuth, Vol II. 

20081201, 14:21  #5 
Aug 2002
Buenos Aires, Argentina
2×17×43 Posts 
If you find errors there feel free to correct them.

20081202, 00:44  #6 
∂^{2}ω=0
Sep 2002
República de California
2^{5}×367 Posts 
There's actually little or no advantage to using a powerof2 base in a floatingbased bigint implementation; one could very well use a power of 10 (or something else  the overall word size is more important than its factorization) in a generic multiprecision library based on floats. Powers of 2 are mainly handy for special moduli (Mersenne and Fermat) and for pureinteger work.

20081202, 04:17  #7 
"Lucan"
Dec 2006
England
2×3×13×83 Posts 
Jeez I'm staying out of this debate

20081202, 12:41  #8  
"Bob Silverman"
Nov 2003
North of Boston
2×3×29×43 Posts 
Quote:
the bits in each word, even in floating point. This results in requiring more limbs to represent each number. Runtime depends on the number of limbs. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
parialgorithm for finding Gaussian integer bases  devarajkandadai  Software  0  20171005 04:54 
parialgorithm for finding Gaussian integer bases  devarajkandadai  Software  0  20170711 05:42 
k*b^n+/c where b is an integer greater than 2 and c is an integer from 1 to b1  jasong  Miscellaneous Math  5  20160424 03:40 
Other Bases?  wblipp  GPU Computing  50  20121011 13:23 
Starting new bases  MrOzzy  Conjectures 'R Us  104  20100318 22:11 