I decided to create a simple worked example of encryption. The first step was to find some large prime numbers so I looked up how to do this on the Internet. Apparently you can use the sieve of Eratosthenes so I wrote the C program below, which uses this method to list all the prime numbers between 2 and 8,000,000:
I redirected the output to a file and the program finished in under 1 second. Here are some of the results from the start, middle and end of the output. I checked them here:
To
solve this puzzle, you place a knight on one of the squares of a chess board
e.g.white's QR1. You then move it around the board visiting each square
once and once only before returning to your chosen starting point.
I wrote a program to do this around 1995 using a DOS based version of Borland Turbo C++.
The
method I used is called Natural-order Tree Searching and is described
in Chapter 6 of Computer Science, A First Course, Second Edition by
Forsythe, Keenan, Organick and Stenberg (ISBN 0-471-26681-7).
Points to note about my solution:
It does not use recursion.
It only uses subscripts >= 1 although arrays in C start with a subscript of zero.
It assumes that 8 moves are possible from every square and then discards any which would send the knight off the board.
It keeps QB2 or QN3 clear until the very end so the knight has a way to get back to the starting point.
During testing, I found that around move 20, white's KR1 was left empty but the squares which could get to it had already been visited. The knight then went backwards and forwards around move 50 but had no hope of ever finding a solution until it had back-tracked to move 20 again, which would not have happened for a very long time. The program was then amended to look for inaccessible squares each time a move was being considered. Once this had been done it was able to calculate a solution in less than a second.
I moved to the south east of England in 1983 to start my career in IT and stayed in a bedsit for a few months. One of the other rooms in the house was also occupied by a programmer and we would occasionally discuss algorithms. I asked him if he knew how numbers like pi or the square root of 2 (for example) were calculated to many decimal places. He explained that the individual digits in such numbers would be stored in arrays and arithmetical calculations would be carried out long hand. This made sense but I was unable to take it any further at the time. It occurred to me that addition and subtraction might be easy enough but long multiplication would take longer to program and long division would be extremely difficult.
I recently found out that Python is able do calculations to great precision and decided to teach myself this language. After a few days I used the method described above to write the program below to work out the square root of two to a little over one million decimal places:
andrew@ASUS-Laptop:~/Python/ROOT2$ cat root2k.py
import mpmath
mpmath.mp.dps = 1000200
root3 = mpmath.mpf (1)
difference = mpmath.mpf (1)
while difference > mpmath.power(10,-1000199):
root1 = mpmath.mpf (root3)
root2 = mpmath.mpf (2 / root1)
root3 = mpmath.mpf ((root1 + root2)/2)
difference = mpmath.fabs (root3 - root1)
if difference <= mpmath.power(10,-1000199):
print ("The square root of two = ")
print " ", root3
andrew@ASUS-Laptop:~/Python/ROOT2$
I ran it like this:
andrew@ASUS-Laptop:~/Python/ROOT2$ date;python root2k.py|fold -w80 > my_output;date
Mon Oct 25 16:26:10 EDT 2021
Mon Oct 25 17:00:31 EDT 2021
andrew@ASUS-Laptop:~/Python/ROOT2$
It took just over 30 minutes to run on an UBUNTU laptop with a Celeron processor. Here is the start of my output (as usual, click on the image to enlarge it / bring it into focus if necessary):
I looked online and found that NASA calculated the square root of two to just over one million decimal places around twenty years ago. You can see their results here. I contacted one of the authors and he confirmed that these results have been checked many times already. Fortunately my results are much the same. The only difference being that, at the end, I have 43 extra decimal places.
I later noticed that NASA also calculated the square root of two to ten million decimal places here. I used this to confirm that my extra 43 decimal places were correct.
You can use pi (or π) to calculate:
(1) The circumference of a circle.
(2) The area of a circle.
(3) The volume of a sphere.
But what is the value of pi?
Pi is irrational so you cannot represent it exactly as a fraction. At school we used 3.14 and 22/7 as rough estimates. There is also a better approximation, which uses a fraction with a 3 figure numerator and denominator but I could not remember it. I looked up pi to several decimal places then worked it out by trial and error with the PL/SQL code below:
SQL> @pi
SQL> set serveroutput on
SQL> declare
2 top number;
3 bottom number;
4 pi constant number := 3.141592654;
5 ratio number;
6 difference number;
7 save_difference number := 1;
8 save_top number;
9 save_bottom number;
10 save_ratio number;
11 begin
12 for top in 1..999 loop
13 for bottom in 1..999 loop
14 ratio := top/bottom;
15 difference := abs(pi-ratio);
16 if difference < save_difference then
17 save_difference := difference;
18 save_top := top;
19 save_bottom := bottom;
20 save_ratio := ratio;
21 end if;
22 end loop;
23 end loop;
24 dbms_output.put_line('Top: '||save_top);
25 dbms_output.put_line('Bottom: '||save_bottom);
26 dbms_output.put_line('Ratio: '||save_ratio);
27 end;
28 /
Top: 355
Bottom: 113
Ratio: 3.14159292035398230088495575221238938053
PL/SQL procedure successfully completed.
SQL>
So there you have it. A better approximation to pi is 355/113, which is accurate to 6 decimal places i.e. 3.141593.
In 1982, I went on a course and learnt to program in BASIC.
I read about the Eight Queens problem on p343 of Computer Science, A First Course, Second Edition. To solve it, you have to place eight queens on a chess board so that none of them can take any of the others. I wrote a Microsoft BASIC program to find all the solutions. In the mid 1980's, it took around 20 minutes to run on an ICL DRS multi-user microcomputer, even when nobody else was using it.
I found it again recently, printed on "pyjama paper". I also located a copy of GWBASIC on a 3.5” floppy disk, typed the program on my home PC and ran it. My PC is almost 10 years old but, even so, it executed the program in about a second. The source code and output are shown below. In case it isn’t obvious, if the program prints 1 5 8 6 3 7 2 4, that means that the queens go on squares a1, b5, c8, d6, e3, f7, g2 and h4.
I mentioned this problem to a colleague at work called Mukesh. He is keen on chess and worked out one possible answer by hand in around 5 minutes. I have put his name beside the solution he found.
10 REM EXAMPLE OF TREE PROCESSING
20 REM
30 REM PROGRAM TO WORK OUT ALL THE DIFFERENT WAYS
40 REM TO PUT 8 QUEENS ON A CHESS BOARD SO THAT
50 REM THEY CANNOT TAKE ONE ANOTHER
60 REM
70 OPEN "SOLUTION" FOR OUTPUT AS #1
80 DIM Q(8,3)
90 FOR J=1 TO 8
100 FOR K=1 TO 3
110 Q(J,K)=0
120 NEXT K
130 NEXT J
140 I=1
150 GOSUB 200
160 GOSUB 390
170 IF I>0 THEN 150
180 CLOSE 1
190 END
200 Q(I,1)=Q(I,1)+1
210 S=0
220 IF Q(I,1)>8 THEN 260
230 GOSUB 270
240 IF S=1 THEN 260
250 GOTO 220
260 RETURN
270 S=1
280 Q(I,2)=(Q(I,1)+I)-1
290 Q(I,3)=(8-Q(I,1))+I
300 IF I=1 THEN 380
310 FOR J=1 TO I-1
320 FOR K=1 TO 3
330 IF Q(J,K)=Q(I,K) THEN S=0
340 NEXT K
350 NEXT J
360 IF S=1 THEN 380
370 Q(I,1)=Q(I,1)+1
380 RETURN
390 IF S=1 THEN 450
400 Q(I,1)=0
410 Q(I,2)=0
420 Q(I,3)=0
430 I=I-1
440 GOTO 520
450 IF I<>8 THEN 510
460 FOR J=1 TO 8
470 PRINT #1,Q(J,1);
480 NEXT J
490 PRINT #1," "
500 GOTO 400
510 I=I+1
520 RETURN
1 5 8 6 3 7 2 4
1 6 8 3 7 4 2 5
1 7 4 6 8 2 5 3
1 7 5 8 2 4 6 3
2 4 6 8 3 1 7 5 <--- Mukesh's solution
2 5 7 1 3 8 6 4
2 5 7 4 1 8 6 3
2 6 1 7 4 8 3 5
2 6 8 3 1 4 7 5
2 7 3 6 8 5 1 4
2 7 5 8 1 4 6 3
2 8 6 1 3 5 7 4
3 1 7 5 8 2 4 6
3 5 2 8 1 7 4 6
3 5 2 8 6 4 7 1
3 5 7 1 4 2 8 6
3 5 8 4 1 7 2 6
3 6 2 5 8 1 7 4
3 6 2 7 1 4 8 5
3 6 2 7 5 1 8 4
3 6 4 1 8 5 7 2
3 6 4 2 8 5 7 1
3 6 8 1 4 7 5 2
3 6 8 1 5 7 2 4
3 6 8 2 4 1 7 5
3 7 2 8 5 1 4 6
3 7 2 8 6 4 1 5
3 8 4 7 1 6 2 5
4 1 5 8 2 7 3 6
4 1 5 8 6 3 7 2
4 2 5 8 6 1 3 7
4 2 7 3 6 8 1 5
4 2 7 3 6 8 5 1
4 2 7 5 1 8 6 3
4 2 8 5 7 1 3 6
4 2 8 6 1 3 5 7
4 6 1 5 2 8 3 7
4 6 8 2 7 1 3 5
4 6 8 3 1 7 5 2
4 7 1 8 5 2 6 3
4 7 3 8 2 5 1 6
4 7 5 2 6 1 3 8
4 7 5 3 1 6 8 2
4 8 1 3 6 2 7 5
4 8 1 5 7 2 6 3
4 8 5 3 1 7 2 6
5 1 4 6 8 2 7 3
5 1 8 4 2 7 3 6
5 1 8 6 3 7 2 4
5 2 4 6 8 3 1 7
5 2 4 7 3 8 6 1
5 2 6 1 7 4 8 3
5 2 8 1 4 7 3 6
5 3 1 6 8 2 4 7
5 3 1 7 2 8 6 4
5 3 8 4 7 1 6 2
5 7 1 3 8 6 4 2
5 7 1 4 2 8 6 3
5 7 2 4 8 1 3 6
5 7 2 6 3 1 4 8
5 7 2 6 3 1 8 4
5 7 4 1 3 8 6 2
5 8 4 1 3 6 2 7
5 8 4 1 7 2 6 3
6 1 5 2 8 3 7 4
6 2 7 1 3 5 8 4
6 2 7 1 4 8 5 3
6 3 1 7 5 8 2 4
6 3 1 8 4 2 7 5
6 3 1 8 5 2 4 7
6 3 5 7 1 4 2 8
6 3 5 8 1 4 2 7
6 3 7 2 4 8 1 5
6 3 7 2 8 5 1 4
6 3 7 4 1 8 2 5
6 4 1 5 8 2 7 3
6 4 2 8 5 7 1 3
6 4 7 1 3 5 2 8
6 4 7 1 8 2 5 3
6 8 2 4 1 7 5 3
7 1 3 8 6 4 2 5
7 2 4 1 8 5 3 6
7 2 6 3 1 4 8 5
7 3 1 6 8 5 2 4
7 3 8 2 5 1 6 4
7 4 2 5 8 1 3 6
7 4 2 8 6 1 3 5
7 5 3 1 6 8 2 4
8 2 4 1 7 5 3 6
8 2 5 3 1 7 4 6
8 3 1 6 2 5 7 4
8 4 1 3 6 2 7 5
