mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2003-03-24, 11:02   #34
cperciva
 
Oct 2002

43 Posts
Default

You're right; it only works if you can find appropriate values for a and b. The usefulness comes from the fact that most big numbers we work with are already in that form: Mersenne numbers, Fermat numbers, Proth numbers, etc are all of the form [something big with a small number of distinct prime factors] +/- 1.
cperciva is offline   Reply With Quote
Old 2003-03-25, 10:35   #35
Cyclamen Persicum
 
Cyclamen Persicum's Avatar
 
Mar 2003

34 Posts
Default

What a crazy stupid rat paranoid am I!!!
Example modulo 1000 does not still work!

Let's multiply 123 by 543 mod 1000.
We are going to use 4-digit FFT.

1000=1024-24.
Then
a = 2^10,
b = 2^3*3

Radix vector is:
(1 4 16 32)

Weight wector is:
(1 6^(1/4) 6^(1/2) 3^(3/4)*2^(-1/4) ),
or
(1.00000000000000 1.56508458007329 2.44948974278318 1.91682931273882)


123 and 543 in radix form are:
(3 2 1 3)
and
(3 3 1 16)

Weighted convolution gives:
(138 72 84 67)

That's 3914

What's the hell?
Please, point me on errors...
Cyclamen Persicum is offline   Reply With Quote
Old 2003-03-25, 17:00   #36
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

1167610 Posts
Default

Quote:
Originally Posted by Cyclamen Persicum
Example modulo 1000 does not still work!
I suggest you work through the length-4 example in the Crandall/Fagin paper
(where the results are known) first, then see about generalizing to other types of moduli.
ewmayer is offline   Reply With Quote
Old 2003-03-25, 18:37   #37
cperciva
 
Oct 2002

2B16 Posts
Default

Quote:
Originally Posted by Cyclamen Persicum
What's the hell?
Please, point me on errors...
1024 and 24 are not relatively prime. You're correctly computing 543*123 modulo (1000/24), but since 1000 and 24 share a factor of 8, this only gives you the value modulo 125 instead of modulo 1000.
cperciva is offline   Reply With Quote
Old 2003-03-26, 09:34   #38
Cyclamen Persicum
 
Cyclamen Persicum's Avatar
 
Mar 2003

34 Posts
Default

Quote:
1024 and 24 are not relatively prime
Thanks a lot! 3^7-1187 does really work.
Cyclamen Persicum is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
why is http://www.mersenne.org/ so slow Unregistered Information & Answers 19 2012-04-17 03:12
Slow Down? R.D. Silverman GMP-ECM 55 2011-10-16 17:28
How hot is too hot? Slow is too slow? petrw1 Hardware 13 2008-11-10 23:25
Slow computer Housemouse Hardware 7 2008-02-15 18:18
Really slow machines? Doorbasher Hardware 5 2004-08-23 22:18

All times are UTC. The time now is 20:06.


Sat Dec 4 20:06:02 UTC 2021 up 134 days, 14:35, 1 user, load averages: 0.92, 0.95, 0.99

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.