The result:
Source file
Header file
Thanks for the help :)
[Edited by - Lode on November 25, 2007 4:19:29 AM]
multiplication in "large" number class
Quote:Original post by LodeOne thing I notice that could simplify some of your code would be to make it a template that allows you to specify the number of ints on each side of the decimal. Then, for the multiply, you could use the basic algorithm I posted but for fixed<3,1> you cast it to fixed<4,1> before the algorithm, use the standard operators for that size, then cast it back afterwards.
The result:
Source file
Header file
Thanks for the help :)
use:
(double)(0x100000000)
instead of:
4294967296.0
?
(Think it would be easier to determine the purpose of the number this way)
(double)(0x100000000)
instead of:
4294967296.0
?
(Think it would be easier to determine the purpose of the number this way)
Quote:Original post by _cdcel
use:
(double)(0x100000000)
instead of:
4294967296.0
?
(Think it would be easier to determine the purpose of the number this way)
That assumes you have a compiler that supports 64bit integer literals.
I.e. don't try that with VS6.
However I agree that it you shouldn't have to type in the maximum value in decimal. I use:
(double(~0U) + 1.0)
I think the most easy and fastest implementation for you problem would be using Karatsube multiplication:
http://en.wikipedia.org/wiki/Karatsuba_algorithm
This way multiplication of 128 bit numbers is based on multiplication of 32 bit numbers. Since the size of big integers is known the multiplication algorithm can be unrolled.
http://en.wikipedia.org/wiki/Karatsuba_algorithm
This way multiplication of 128 bit numbers is based on multiplication of 32 bit numbers. Since the size of big integers is known the multiplication algorithm can be unrolled.
Author
Quote:Original post by nmi
I think the most easy and fastest implementation for you problem would be using Karatsube multiplication:
http://en.wikipedia.org/wiki/Karatsuba_algorithm
This way multiplication of 128 bit numbers is based on multiplication of 32 bit numbers. Since the size of big integers is known the multiplication algorithm can be unrolled.
It looks like a good algorithm for even larger numbers, but mine aren't large enough yet:
Quote:Implementations differ greatly on what the crossover point is when Karatsuba becomes faster than the classical algorithm, but generally numbers over 2^320 are faster with Karatsuba. [1][2] Toom-Cook multiplication is a faster generalization of Karatsuba's, and is further surpassed by the Schönhage-Strassen algorithm.
Mine are only up to 2^128 :)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
