mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2005-11-29, 04:43   #1
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5·701 Posts
Default Idea about 10,000,000 digit attempt.

First let me say, I don't come here often, so if my idea is already used or been discussed please send me a PM about it and lock the thread. Anyhow, I didn't want to have to deal with Mr. Silverman, and I figured people in this forum would have a better idea about this than the regular math folks(mind you I've forgotten everything I've even learned about programming).

But, as to my idea:I'm of the opinion that people are sieving and checking 2^n-1 in their attempt to collect the money(or simply be in the record books). But isn't it true that when it comes to LLR, when you do k*2^n-1, k's from 1 to 31 don't change the time taken much at all? So you would have 31 times as many opportunities for the same amount of work.

Am I missing something?
jasong is offline   Reply With Quote
Old 2005-11-29, 05:22   #2
axn
 
axn's Avatar
 
Jun 2003

23×607 Posts
Default

Quote:
Originally Posted by jasong
But, as to my idea:I'm of the opinion that people are sieving and checking 2^n-1 in their attempt to collect the money(or simply be in the record books). But isn't it true that when it comes to LLR, when you do k*2^n-1, k's from 1 to 31 don't change the time taken much at all? So you would have 31 times as many opportunities for the same amount of work.
I don't have any specific benchmarks, but I believe there is a significant speed difference between 2^n-1 and k*2^n-1, even for such small k's. Also k=1,2,4,8 and 16 belong to the 2^n-1 family only
axn is online now   Reply With Quote
Old 2005-11-29, 11:23   #3
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

Quote:
Originally Posted by jasong
But isn't it true that when it comes to LLR, when you do k*2^n-1, k's from 1 to 31 don't change the time taken much at all?
Doesn't "don't change the time" apply to each individual k, rather than to all k collectively? That is, 3*2^n-1 takes the same time as 5*2^n-1, but not the same time as 3*2^n-1 AND 5*2^n-1 together.

Perhaps I'm overlooking something myself, but I think that, in general, sieving on 2^n-1 does not help factor 3*2^n-1 or 5*2^n-1 or any other k*2^n-1 with odd k.

Last fiddled with by cheesehead on 2005-11-29 at 11:25
cheesehead is offline   Reply With Quote
Old 2005-11-29, 15:59   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by cheesehead
Doesn't "don't change the time" apply to each individual k, rather than to all k collectively? That is, 3*2^n-1 takes the same time as 5*2^n-1, but not the same time as 3*2^n-1 AND 5*2^n-1 together.

Perhaps I'm overlooking something myself, but I think that, in general, sieving on 2^n-1 does not help factor 3*2^n-1 or 5*2^n-1 or any other k*2^n-1 with odd k.
You are correct. Processing k*2^n - 1 for small odd k is just slightly slower
than 2^n-1. Reducing a product mod k*2^n-1 requires a single
multiplication of half of the product by k, followed by a subtraction.

But one must check eack k.
R.D. Silverman is offline   Reply With Quote
Old 2005-11-29, 22:24   #5
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

22·11·167 Posts
Default

Quote:
Originally Posted by R.D. Silverman
Reducing a product mod k*2^n-1 requires a single multiplication of half of the product by k, followed by a subtraction.
You can even use a DWT. This adds log2(k) bits per double. So for very small k, 2^n-1 and k*2^n-1 often use the same FFT length. That is, at equal speed to an LL test.
Prime95 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Windows 10 in Ubuntu, good idea, bad idea, or...? jasong jasong 8 2017-04-07 00:23
setting up wakeon lan attempt 4 wildrabbitt Hardware 0 2016-05-22 17:22
New Year's all 24 zones attempt jasong Lounge 29 2007-01-01 19:00
idea about 10 million digit search(possibly dumb) jasong Math 5 2006-06-07 10:39
Factorization attempt on 100^99+99^100 JHansen Factoring 34 2005-05-27 19:24

All times are UTC. The time now is 08:40.

Thu Feb 25 08:40:40 UTC 2021 up 84 days, 4:51, 0 users, load averages: 1.64, 1.54, 1.56

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.