2. Computation techniques 1

The compatation order of the algorithm of previous page is o(n).
If we want to compute one more digit, we need 10 times of computation.
We need some advanced method.

Method 1 : noticing the lower half digits

The lower n digits of b=a² is determined just lower n digits of a.
When we check some number and if we get four digits in the lower 5 digits,
we do not need to check further digits.

So, for example, each g as 1 ≤ g ≤ 99999 and lower 5 digits of g² is less than 3 digits store to array w[i], and check only

a=100000*h+w[i], h:arbitrary.

This method reduces the loop times.

The area of array w[i] can be reduced, as

(100000+g)²=10¹⁰+200000g+g²
(100000-g)²=10¹⁰-200000g+g²

lower 5 digits of (100000+g)² and (100000-g)² are same.
So the range of g is just 100001 ≤ g ≤ 149999.
And,

(50000-g)²=25*10⁸-100000g+g²

lower 5 digits of g² and (50000-g)² are same.
So the range of g is just 100001 ≤ g ≤ 124999.

The algorithm are following

    for g=100001 to 124999
      check the lower 5 digits of g^2.
      If it is less than 3 digits, store g@100000 in the w[i].
    next g

    h=0
*   for i=1 to m : a=100000h+w[i] : gosub ** : next i
    for i=m to 1 step -1 : a=100000h+50000-w[i] : gosub ** : next i
    for i=1 to m : a=100000h+50000+w[i] : gosub ** : next i
    for i=m to 1 step -1 : a=100000h+100000-w[i] : gosub ** : next i
    inc h : goto *

**  ' check routine
    If b=a2 is consisted of 3 digits,
      print a, b
    return