mersenneforum.org > Math Understanding Lucas' chess board algorithm
 Register FAQ Search Today's Posts Mark Forums Read

 2017-03-25, 09:53 #1 a nicol   Nov 2016 29 Posts Understanding Lucas' chess board algorithm I'm trying to understand the chess board algorithm that Lucas used compute the residues of Mersenne numbers. For example, the calculation of residues for 2^7-1: Form the sequence of numbers S_n = 3, 7, 47, ... via squaring, subtracting 2, and reduction modulo the Mersenne number. If we perform this on S_3 to obtain S_4 using binary multiplication, we can lay out the calculation on a 7 x 7 chess board (noting how 0101111 is left shifted through the rows cyclically), then obtain the result of the reduction. 0 1 0 1 1 1 1 = S_3 = 47 7 6 5 4 3 2 1 0 1 0 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 0 1 0 1 0 0 0 0 0 0 0 1 1 0 1 0 1 1 Once he had this array, Lucas would perform these operations: 1: Subtract 2 from the result via removing one pawn from column 2. 2: For each pair of pawns in any column, remove one from the board and move the other into the column to the left. Via successive removal of lines, continue these operations until the only pawns remaining are in the first row. In our case we are supposed to get a top row of: 7 6 5 4 3 2 1 0 1 1 0 0 0 0 = S_4 = 48 = 2207 mod 127 I would be grateful for a more detailed description of the second instruction or additional procedures. I can't seem to get the right result. How does one remove and shift the pawns to obtain the top row? I've attached a clipping of an explanation from "Mathematics of Computation 1943-1993" and the 127 bit array from Lucas' paper in Recreations Mathematiques - https://primes.utm.edu/mersenne/Luke...t/lit_068s.htm Lucas shows an additional set of four rows giving the addition of the units of each column, with the carries, but I'm not clear if/how these are accumulated using pawns. Attached Thumbnails
 2017-03-25, 19:22 #2 a nicol   Nov 2016 1D16 Posts Sorry, the array from Lucas' paper is 31 bits, not 127 (but he did prove 2^127 -1 is prime using this method). Last fiddled with by a nicol on 2017-03-25 at 19:23
 2017-03-25, 19:28 #3 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 26·31 Posts Thank you for posting this thread. I have subscribed to it for further study. BTW, Welcome to the board.
 2017-03-25, 21:31 #4 science_man_88     "Forget I exist" Jul 2009 Dumbassville 26×131 Posts the closest method I know of is that you can square a number using shifts and carries in binary: 11111 -> 31 in binary $\begin{tabular}{l | c} 0000011111&31\\ 0000111110&62\\ 0001111100&124\\ 0011111000&248\\ 0111110000&496\\ \hline 1111000001&961\\ \end{tabular}$ but as for what's actually being done I'm at a loss right now. Last fiddled with by science_man_88 on 2017-03-25 at 21:51
 2017-03-26, 00:12 #5 science_man_88     "Forget I exist" Jul 2009 Dumbassville 838410 Posts sorry double posting it seems to be missing one of the shifts and replaced it with 0 or messed it up but one formula is y mod 2^n-1 is equivalent to y mod 2^n + y\(2^n) where \ is the integer division sign. You get the addition of the two parts, if you shift the binary value correctly.
2017-03-26, 17:26   #6
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

13·491 Posts

Quote:
 Originally Posted by a nicol I'm trying to understand the chess board algorithm that Lucas used compute the residues of Mersenne numbers. For example, the calculation of residues for 2^7-1: Form the sequence of numbers S_n = 3, 7, 47, ... via squaring, subtracting 2, and reduction modulo the Mersenne number. If we perform this on S_3 to obtain S_4 using binary multiplication, we can lay out the calculation on a 7 x 7 chess board (noting how 0101111 is left shifted through the rows cyclically), then obtain the result of the reduction. 0 1 0 1 1 1 1 = S_3 = 47 Code: 7 6 5 4 3 2 1 0 1 0 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 0 1 0 1 0 0 0 0 0 0 0 1 1 0 1 0 1 1
I don't think the article has the correct initial configuration for the board!

You're trying to compute 0101111^2 mod 127. That is, (32+8+4+2+1)*47 mod 127.

Which is 47 + 2*47 + 4*47 + 8*47 + 32*47

So I would start out on the board with

Code:
0101111   = 47
1011110   = 2*47
0111101   = (4*47)%127  where the modulo comes from the cyclic shift
1111010   = (8*47)%127
0000000  because not 16*47
1101011  = (32*47)%127
0000000  because not 64*47
which isn't quite what the board in the article is.

And the rules need to be (these are 'adding zero or 2^p-1 does nothing', 'addition is commutative', and 'twice a power of two is the next power of two')

* If a row is all-empty or all-full, you can remove it and move all the other rows up
* You can move a pawn up and down its column at will
* If there are ever two 1s in a column, you can remove them both and change a 0 to a 1 in the next column (they don't have to be adjacent or anything). This includes wrapping round from the leftmost to the rightmost column

I set this up in Excel with some extra calculations to check that I wasn't changing the answer, and did manage correctly to square 47 mod 127. I think the original article doesn't make it clear that the pawns you remove don't have to be adjacent in their column and that the increment can be anywhere in the appropriate column, and I really don't think they've illustrated the starting board correctly.

Last fiddled with by fivemack on 2017-03-26 at 17:27

 2017-03-27, 16:30 #7 LaurV Romulan Interpreter     Jun 2011 Thailand 52×7×53 Posts To make it chess-like, imagine a game of suicidal lemmings, where the chessboard is on the side of a cliff and all pawns/lemmings advance towards the cliff. So, better rules could be: - if a pawn has an empty square in front of him, he advances into it. - if a pawn can not advance because other pawn is in front of him, he will "capture" (kill) the one in front of him by moving himself to the left, if the left square is free (this cycles as mentioned, from the first column to the last) (alternative, you can say that when a pawn can not advance because other pawn is in front of him, he will push that one to the left, if the space is empty, but doing so, he will die because of the effort, hehe). - if the first row is full, all pawns hold their hands and jump from the clif, crying "hooraay" hehehe. Of course, a prime is the most criminal situation, where all pawns comit suicide. Note that "subtracting 2" may not be possible initially, therefore it has to be done first time when it becomes possible (i.e. remove a pawn from the second column from the right). It is very easy to implement an animation of it... (maybe we will do one in excel or so, but not now, when it is midnight here). Last fiddled with by LaurV on 2017-03-27 at 16:32
 2017-03-28, 11:08 #8 a nicol   Nov 2016 1D16 Posts Thank you for your responses all. I can get the right answer now. Thank you for the correction to the table fivemack: Mathematics of Computation, 1943-1993: A Half-century of Computational Mathematics has a mistake in it, I think. Being able to move the pawns up and down and clear out a whole full row at once makes this much easier. Last fiddled with by a nicol on 2017-03-28 at 12:07

 Similar Threads Thread Thread Starter Forum Replies Last Post Raman Chess 6 2016-12-06 06:50 Fred PrimeNet 3 2016-05-19 13:40 Demonslay335 YAFU 11 2016-01-08 17:52 wildrabbitt Math 1 2015-05-17 12:34 zacariaz Homework Help 32 2007-05-16 15:18

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

Mon Mar 8 20:18:48 UTC 2021 up 95 days, 16:30, 1 user, load averages: 1.25, 1.42, 1.42