I'll agree that the your ideas would lead to speed-ups, but compared to the difference between the current O(n^2) multiplication and the O(n*^.n) FFT muliplication those would be minor.
I suspect that for large integer y, n|x^y would be much more common than x^n. ----- Original Message ----- From: [email protected] Date: Wednesday, July 6, 2011 14:54 Subject: Integer Powers WAS: Large numbers To: Programming forum <[email protected]> Cc: Roger Hui <[email protected]> > Thinking out loud, > > If there is an FFT implementation, there might be some speedups > for integer powers > of large integers: > > 0. In x^y, you would need to compute the transform of x only once; > > 1. Similarly, the transforms of other powers that are to be > reused could be saved; > > 2. It might be possible to calculate x^3 or x^4 rather than x^2, > by taking that > power of the transform, if the radix permits (the > precision of a double would > be the limiting factor). > > I'm just saying, > > Henry Rich > > ---- Roger Hui <[email protected]> wrote: > > The repeated squaring still needs a large multiplication > > of numbers with each with about 2357207%2 digits. > > This alone would take considerable time with the > > current non-FFT multiplication. > > > > The example in the Jwiki essay indicates that > > two million-digit numbers would take about 23 seconds. > > In contrast: > > > > timer 'x*y' [ x=: ?10x^e [ y=: ?10x^e=: 1e4 > > 0.0486372 > > timer 'x*y' [ x=: ?10x^e [ y=: ?10x^e=: 2e4 > > 0.286935 > > timer 'x*y' [ x=: ?10x^e [ y=: ?10x^e=: 4e4 > > 0.882918 > > timer 'x*y' [ x=: ?10x^e [ y=: ?10x^e=: 8e4 > > 3.2742 > > timer 'x*y' [ x=: ?10x^e [ y=: ?10x^e=: 16e4 > > 12.9076 > > > > Looks like doubling the number of digits requires > > quadrupling the time, so 1e6 digits would take > > about 12.9076*4^3 or 827 or so seconds. > > > > > > > > ----- Original Message ----- > > From: [email protected] > > Date: Wednesday, July 6, 2011 10:18 > > Subject: Re: [Jprogramming] Large numbers > > To: Programming forum <[email protected]> > > Cc: Roger Hui <[email protected]> > > > > > 0. One of these numbers needs to have an x to get extended > > > precision. > > > 1. 28433 * 2^7830457 + 1 > > > > > > is the same as > > > > > > 28433 * 2^7830458 > > > > > > which seems unlikely to be what was meant. > > > > > > 2. Roger, isn't the power done by repeated squaring or > > > some such trick? > > > So the power will take about 30-50 multiplications whose > > > average length^2 is around 1500000^2, right? That > > > could give an estimate > > > of the expected time. > > > > > > Henry Rich > > > > > > ---- Roger Hui <[email protected]> wrote: > > > > The multiplication is currently O(n^2) so the number > > > > you described will take a very long time. How long? > > > > You can gauge it by timing the multiplication of > > > > numbers with 1e4, 2e4, 4e4, etc. digits. > > > > > > > > The multiplication would be faster with: > > > > http://www.jsoftware.com/jwiki/Essays/FFT > > > > > > > > > > > > > > > > ----- Original Message ----- > > > > From: David Vaughan <[email protected]> > > > > Date: Wednesday, July 6, 2011 8:32 > > > > Subject: [Jprogramming] Large numbers > > > > To: Programming forum <[email protected]> > > > > > > > > > Hi, what's the largest number J can compute? > > > > > I'm looking to compute 28433 * 2^7830457 + 1, which has > > > 2357207 > > > > > digits. I started calculating it, but it's taking a very > > > long > > > > > time (obviously), an I'm wondering how long it's likely > to > > > take, > > > > > and whether it's even possible. ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
