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

16778 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

3×52×7 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

5068 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
 
Aug 2002

22·32·5·47 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

7×137 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

2×163 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

23·5·283 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

83·127 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 00:48.


Sat May 28 00:48:07 UTC 2022 up 43 days, 22:49, 0 users, load averages: 1.93, 1.82, 1.78

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”