Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #8987

Re: Large number multiplication

From Christian Heimes <lists@cheimes.de>
Subject Re: Large number multiplication
Date 2011-07-06 22:43 +0200
References <iv2d7n$ksv$1@speranza.aioe.org> <mailman.722.1309982770.1164.python-list@python.org> <iv2frn$rte$1@speranza.aioe.org>
Newsgroups comp.lang.python
Message-ID <mailman.725.1309984999.1164.python-list@python.org> (permalink)

Show all headers | View raw

Am 06.07.2011 22:15, schrieb Billy Mays:
> I believe it is possible to do FFTs without significant rounding error. 
>   I know that the GIMPS's Prime95 does very large multiplications using 
> FFTs (I don't know if they use the integer based or double based 
> version).  I also know they have guards to prevent rounding errors so I 
> don't think it would be impossible to implement.

It might work for medium large longs but how about really large longs
like 5 * 1,000**10,000? I'm not familiar with FFT based multiplication
but I guess that very large numbers are going to introduce rounding
errors if floating points are involved.

Python used to run on platforms without an FPU and floats. These days
Python might still run on platforms with just an emulated FPU. Unless
there is a way to implement FFT without floating point ops, an emulated
or missing FPU makes FFT slower than Karatsuba. There might be one but I
haven't learned a way in my numerics classes.

Christian

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Large number multiplication Billy Mays <noway@nohow.com> - 2011-07-06 15:30 -0400
  Re: Large number multiplication Ian Kelly <ian.g.kelly@gmail.com> - 2011-07-06 14:02 -0600
    Re: Large number multiplication Billy Mays <noway@nohow.com> - 2011-07-06 16:21 -0400
      Re: Large number multiplication Ian Kelly <ian.g.kelly@gmail.com> - 2011-07-06 14:37 -0600
      Re: Large number multiplication Ulrich Eckhardt <ulrich.eckhardt@dominolaser.com> - 2011-07-07 10:30 +0200
        Re: Large number multiplication Ian Kelly <ian.g.kelly@gmail.com> - 2011-07-07 09:49 -0600
        Re: Large number multiplication Ian Kelly <ian.g.kelly@gmail.com> - 2011-07-07 09:50 -0600
        Re: Large number multiplication casevh <casevh@gmail.com> - 2011-07-07 10:46 -0700
        Re: Large number multiplication Mark Dickinson <mdickinson@enthought.com> - 2011-07-08 00:31 -0700
      Re: Large number multiplication Parerga <nabble.com@bodrato.it> - 2011-07-07 09:00 -0700
  Re: Large number multiplication Christian Heimes <lists@cheimes.de> - 2011-07-06 22:05 +0200
    Re: Large number multiplication Billy Mays <noway@nohow.com> - 2011-07-06 16:15 -0400
      Re: Large number multiplication Christian Heimes <lists@cheimes.de> - 2011-07-06 22:43 +0200
    Re: Large number multiplication Nobody <nobody@nowhere.com> - 2011-07-07 01:33 +0100

csiph-web