> I suspect that for large integer y, n|x^y would be much > more common than x^n.
Typo: I meant to say: I suspect that for large integer y, n|x^y would be much more common than x^y. ----- Original Message ----- From: Roger Hui <[email protected]> Date: Wednesday, July 6, 2011 15:29 Subject: Re: [Jprogramming] Integer Powers WAS: Large numbers To: Programming forum <[email protected]> > 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
