 mersenneforum.org > Math Finding the square root of a large mersenne number
 Register FAQ Search Today's Posts Mark Forums Read  2003-09-08, 02:15 #1 Fusion_power   Aug 2003 Snicker, AL 16778 Posts 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   2003-09-08, 02:56 #2 Joe O   Aug 2002 3×52×7 Posts A good first approximation to sqrt(2^33349067-1) would be 1.414*2^166724533   2003-09-08, 02:59 #3 Joe O   Aug 2002 3×52×7 Posts A good first approximation to sqrt(2^33349067-1) would be 1.414*2^16674533 Why can't we edit posts in this forum?   2003-09-08, 04:49 #4 tom11784   Aug 2003 Upstate NY, USA 5068 Posts they've disabled editting for regular users to try to deal with speed issues from what i understand   2003-09-08, 06:25 #5 Xyzzy   Aug 2002 22·32·5·47 Posts Yes, please check the message preview before you commit! :)   2003-09-08, 07:15   #6

"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts 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   2003-09-08, 12:53 #7 Fusion_power   Aug 2003 Snicker, AL 7×137 Posts 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   2003-09-08, 16:18 #8 tom11784   Aug 2003 Upstate NY, USA 2×163 Posts factors can only be congruent to 1 or 7 mod 8   2003-09-08, 16:23   #9
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

23·5·283 Posts 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   2003-09-09, 00:14 #10 apocalypse   Feb 2003 2·3·29 Posts 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.   2003-09-09, 04:28 #11 Uncwilly 6809 > 6502   """"""""""""""""""" Aug 2003 101×103 Posts 83·127 Posts 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    Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post chris2be8 Msieve 13 2020-10-14 07:08 paul0 Factoring 10 2015-01-19 12:25 Damian Math 3 2010-01-01 01:56 Fusion_power Math 19 2007-11-02 21:37 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