Re: A brand new calculator benchmark: "middle square method seed test"
Message #5 Posted by Pier Aiello on 11 Sept 2013, 4:18 p.m.,
in response to message #4 by Gilles Carpentier
Of course, and i use wikipedia for this (since it was my main source (1)). Given the notions in the Middle-square Wikipedia article we have that the middle square method has a lot of flaws because the sequence can be convergent or cyclic really fast. An example:
Let k=1 , so we have as reference n:= 100^k = 100
Do sequences for all the seeds from a:=n/10 to n-1.
So the seeds are {a:=10,11,12,...,99}
How do we compute a sequence?
a:=10
seed:=a
1. we first square the number
10*10 = 100
2. But our reference is 100, so 100 squared is 10000, with 4 zeroes, then we consider the number with four digits (with a leading zero)
0100
3. Then we pick the middle digits, as many as the zeroes of n (that is 100), the new seed is
0[10]0
4. But the new seed is the same as the initial seed, then if we reapply the process we end up always with 10. Then the sequence is convergent.
Next step
a:=11
seed:=a
seed^2 -> 121
See it with 4 digits -> 0121
Pick middle digits -> 0[12]1 , seed:= 12
seed^2 -> 144
See it with 4 digits -> 0144
Pick middle digits -> 0[14]4, seed:=14
seed^2 -> 196
See it with 4 digits -> 0196
Pick middle digits -> 0[19]6, seed:=19
seed^2 -> 361
See it with 4 digits -> 0361
Pick middle digits -> 0[36]1, seed:=36
seed^2 -> 1296
See it with 4 digits -> 1296
Pick middle digits -> 1[29]6, seed:=29
seed^2 -> 841
See it with 4 digits -> 0841
Pick middle digits -> 0[84]1, seed:=84
seed^2 -> 7056
See it with 4 digits -> 7056
Pick middle digits -> 7[05]6, seed:=5
seed^2 -> 25
See it with 4 digits -> 0025
Pick middle digits -> 0[02]5, seed:=2
seed^2 -> 4
See it with 4 digits -> 0004
Pick middle digits -> 0[00]4, seed:=0
seed^2 -> 0
See it with 4 digits -> 0000
Pick middle digits -> 0[00]0, seed:=0
Here the new seed is the same of the previous, so the process stops
let's skip some iterations
a:=24
seed:=a
seed^2 -> 576
See it with 4 digits -> 0576
Pick middle digits -> 0[57]6, seed:=57
seed^2 -> 3249
See it with 4 digits -> 3249
Pick middle digits -> 3[24]9, seed:=24
At this time you can do an infinite loop that is cyclic,
so i limit any sequence to max 100^k iterations (2).
(1) I want to design a "simple" benchmark, so i thought about the extraction of numbers from a random sequence, or better, from decimals of transcendental numbers. So i stumbled on Bailey–Borwein–Plouffe formula, but it is a bit complex so i prefer a simpler method.
(2)Yes, i miss the phrase For a generator of n-digit numbers the period can be no longer than 8^n, now it is late and moreover this is a benchmark so the more computations, the better challenge for fast calculators.
Edited: 11 Sept 2013, 8:05 p.m. after one or more responses were posted
| 
Go back to the main exhibit hall