mersenneforum.org  

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

Reply
 
Thread Tools
Old 2003-09-08, 02:15   #1
Fusion_power
 
Fusion_power's Avatar
 
Aug 2003
Snicker, AL

3BF16 Posts
Default Finding the square root of a large mersenne number

I am trying to figure out how long it would take to find the square root of say a 10 million digit number. I am currently testing exponent 33,349,067. What would be the fastest code method of determining the square root? I think I can show this in math pseudo better than I can explain it.

(a 10 million digit number) q = (2^33349067-1)
(the square root of q) srq = sqrt (q)
(the remainder after subtracting the square from the number) rmd = q - (srq^2)

My interest is based on the current method of trial factoring. If I have the math down correctly, the number of potential factors of a Mersenne number is severely limited. Would a squares based algorithm potentially use fewer steps to find factors than the current method shown on http://www.mersenne.org/math.htm ?

Thanks,

Fusion
Fusion_power is offline   Reply With Quote
Old 2003-09-08, 02:56   #2
Joe O
 
Joe O's Avatar
 
Aug 2002

3·52·7 Posts
Default

A good first approximation to sqrt(2^33349067-1) would be 1.414*2^166724533
Joe O is offline   Reply With Quote
Old 2003-09-08, 02:59   #3
Joe O
 
Joe O's Avatar
 
Aug 2002

52510 Posts
Default

A good first approximation to sqrt(2^33349067-1) would be 1.414*2^16674533

Why can't we edit posts in this forum?
Joe O is offline   Reply With Quote
Old 2003-09-08, 04:49   #4
tom11784
 
tom11784's Avatar
 
Aug 2003
Upstate NY, USA

2×163 Posts
Default

they've disabled editting for regular users to try to deal with speed issues from what i understand
tom11784 is offline   Reply With Quote
Old 2003-09-08, 06:25   #5
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

2×4,019 Posts
Default

Yes, please check the message preview before you commit! :)
Xyzzy is offline   Reply With Quote
Old 2003-09-08, 07:15   #6
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default Re: Finding the square root of a large mersenne number

Quote:
Originally Posted by Fusion_power
My interest is based on the current method of trial factoring. If I have the math down correctly, the number of potential factors of a Mersenne number is severely limited. Would a squares based algorithm potentially use fewer steps to find factors than the current method shown on http://www.mersenne.org/math.htm ?
Are you speaking, perhaps, of "Fermat's factoring method" or "Kraitchik's method"? Fermat's method tries to find two numbers whose squares differ by a multiple of the number to be factored. Kraitchik found a way to speed up Fermat's method. See Math 511, Fermat's Factoring Method at http://www.math.ksu.edu/math511/notes/925.html
cheesehead is offline   Reply With Quote
Old 2003-09-08, 12:53   #7
Fusion_power
 
Fusion_power's Avatar
 
Aug 2003
Snicker, AL

16778 Posts
Default

Cheesehead,

Yes, but no. Fermat understood something important about finding the factorization of a number. What he did was organize a number into a matrix then analyze the matrix for its prime constituents. In its current implementation it would be useless on mersenne numbers.

I think a mersenne specific optimization could be coded. Thats the reason I am trying to figure out the time required to find the square root of a very large number.

What would qualify as a mersenne specific optimization? To start with it would only permit factors of the form 2kp+1.

Fusion
Fusion_power is offline   Reply With Quote
Old 2003-09-08, 16:18   #8
tom11784
 
tom11784's Avatar
 
Aug 2003
Upstate NY, USA

14616 Posts
Default

factors can only be congruent to 1 or 7 mod 8
tom11784 is offline   Reply With Quote
Old 2003-09-08, 16:23   #9
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

246248 Posts
Default

Quote:
Originally Posted by Fusion_power
Cheesehead,

Yes, but no. Fermat understood something important about finding the factorization of a number. What he did was organize a number into a matrix then analyze the matrix for its prime constituents. In its current implementation it would be useless on mersenne numbers.

I think a mersenne specific optimization could be coded. Thats the reason I am trying to figure out the time required to find the square root of a very large number.

What would qualify as a mersenne specific optimization? To start with it would only permit factors of the form 2kp+1.

Fusion
It is extremely unlikely that this method would work for Mersenne numbers. You are describing Fermat's method, admittedly sped up by a factor of (2kp+1) or more, but unless the factors are very close together (i.e. unless they differ by at most a few times the 4th root of the number you are trying to factor) Fermat's method will not find the factors in a reasonable time.

Try implementing it, by all means, but test it on small Mp first. You will find it useless for p as small as 500, where we can already factor Mersenne numbers by other algorithms. The run time get worse, much worse, as p increases.


Paul
xilman is offline   Reply With Quote
Old 2003-09-09, 00:14   #10
apocalypse
 
Feb 2003

2·3·29 Posts
Default

Fusion_power -

Here's a fairly straightforward square root algorithm I wrote for the java.math.BigInteger class as it doesn't have one already...

I'm sure there are faster algorithms, but this one is quadratic, which isn't too bad.

[code:1]
public BigInteger sqrt(BigInteger n) {
int currBit = n.bitLength() / 2;

BigInteger remainder = n;
BigInteger currSquared = BigInteger.ZERO.setBit(2*currBit);

BigInteger temp = BigInteger.ZERO;
BigInteger toReturn = BigInteger.ZERO;

BigInteger potentialIncrement;
do {
temp = toReturn.setBit(currBit);
potentialIncrement = currSquared.add(toReturn.shiftLeft(currBit+1));

int cmp = potentialIncrement.compareTo(remainder);
if (cmp < 0) {
toReturn = temp;
remainder = remainder.subtract(potentialIncrement);
}
else if (cmp == 0) {
return temp;
}
currBit--;
currSquared = currSquared.shiftRight(2);
} while (currBit >= 0);
return toReturn;
}
[/code:1]

Some timings:
[code:1]
2^33349 - 1
sqrt takes 1109 ms

2^333490 - 1
sqrt takes 161891 ms
[/code:1]
on my Athlon XP, which extrapolates to 6-7 weeks for 2^33349067 - 1, so I would recommend finding a better sqrt algorithm.
apocalypse is offline   Reply With Quote
Old 2003-09-09, 04:28   #11
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101Γ—103 Posts

224148 Posts
Default

Could I suggest the old fashioned method?

Get that program that will expand 2^33349067-1 to its decimal equivalent. Then write (I think that I could do it, but don't quote me) and run a simple program that takes the square root the by hand method. The only critical part should be knowing if it has an even or odd number of digits.

Si o No
Uncwilly is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
All square roots failed chris2be8 Msieve 13 2020-10-14 07:08
NFS Square root problems paul0 Factoring 10 2015-01-19 12:25
Square root of 3 Damian Math 3 2010-01-01 01:56
Fastest possible algorithm to calculate the square root of a 10,000,000 digit number Fusion_power Math 19 2007-11-02 21:37
Divisible up to Square Root davar55 Puzzles 3 2007-09-05 15:59

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

Fri Apr 16 14:08:32 UTC 2021 up 8 days, 8:49, 0 users, load averages: 1.89, 1.80, 1.71

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.