mersenneforum.org  

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

Reply
 
Thread Tools
Old 2017-03-25, 09:53   #1
a nicol
 
Nov 2016

29 Posts
Default 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
Click image for larger version

Name:	lucas-binary.PNG
Views:	110
Size:	123.0 KB
ID:	15820   Click image for larger version

Name:	lucas127residues.PNG
Views:	95
Size:	107.2 KB
ID:	15821  
a nicol is offline   Reply With Quote
Old 2017-03-25, 19:22   #2
a nicol
 
Nov 2016

1D16 Posts
Default

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
a nicol is offline   Reply With Quote
Old 2017-03-25, 19:28   #3
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

26·31 Posts
Default

Thank you for posting this thread.

I have subscribed to it for further study.

BTW, Welcome to the board.
a1call is offline   Reply With Quote
Old 2017-03-25, 21:31   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

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} <br />
0000011111&31\\<br />
0000111110&62\\<br />
0001111100&124\\<br />
0011111000&248\\<br />
0111110000&496\\<br />
\hline<br />
1111000001&961\\<br />
\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
science_man_88 is offline   Reply With Quote
Old 2017-03-26, 00:12   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 Posts
Default

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.
science_man_88 is offline   Reply With Quote
Old 2017-03-26, 17:26   #6
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

13·491 Posts
Default

Quote:
Originally Posted by a nicol View Post
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
fivemack is offline   Reply With Quote
Old 2017-03-27, 16:30   #7
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

52×7×53 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2017-03-28, 11:08   #8
a nicol
 
Nov 2016

1D16 Posts
Default

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
a nicol is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Vote chess game 4: To be decided? Some chess variant will be interesting to consider with! Raman Chess 6 2016-12-06 06:50
Understanding assignment rules Fred PrimeNet 3 2016-05-19 13:40
Understanding NFS Demonslay335 YAFU 11 2016-01-08 17:52
understanding the group G in an explanation of the Lucas-Lehmer test wildrabbitt Math 1 2015-05-17 12:34
LL Test: Understanding the math 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

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.