Inferno #04 22 июня 2003

Программирование

For Coderz - An algorithm for finding the integer part of square root.

            Square root.

(C) Alone Coder



  On this subject, I spent the better week:)
Still split Bezbashenny algorithm
Spent the whole of the square root
where something moves-subtract-shift-subtracted ... and why it 
turns correct result:)


  I hope everyone saw the compiler MCODER2
or at least something else, where no comment is given, this 
SQR? (And then suddenly I so rejoice in vain, and readers are 
looking at these large letters with big eyes, wondering what it 
is I ate that such a happy? ;) 


   Here's the procedure:

; HL = N argument

     OR A

     LD A, L

     LD L, H

     LD DE, 64

     LD H, D

     LD B, 8
sqr0 SBC HL, DE

     JR NC, $ +3

     ADD HL, DE

     CCF

     RL D

     ADD A, A

     ADC HL, HL

     ADD A, A

     ADC HL, HL

     DJNZ sqr0
; D = result q = [√ N].
; The end of the movie. Thank you for your attention;)


   You will understand the procedure in this way? That's right, 
no I do not poymete.I poymu.I the more 're skeptical about the 
idea of ​​her use, especially not verify the validity of all 
numbers from 0 to 32767. And to increase the capacity the more 
results you will not take, not knowing how to program will work 
after that. 


              The first step.


   All self-respecting programmer knows that the square of the 
integer q can be represented as a sum of consecutive odd 
numbers from one to 2q-1. 

   Only retrieved through a square
root (by subtracting the increasing odd, until they cease to be 
deducted) too, perhaps wasteful.



             Read a book.


   The first hint I found here:
(J. Arsaces Programming of games and puzzles, word for word)


  "We can generalize the previous algorithm, using the 
properties of decimal numbers. This number is divided into two 
pieces figures from the right, then we start

subtract consecutive odd numbers
from the extreme left of the piece:


  1909 1809 1509 1009
 - 1 - 3 - 5 - 7

  ---- ---- ---- ---
  1809 1509 1009 309


  If it can not continue further, then
Recently subtrahend number increases
per unit, is shifted one step to the right, and
after her assigned unit. That -
the first odd number, which should be subtracted from the 
previous balance. 

  In the example above, 7 +1 = 8; attributing 1, we get 81 and 
continue: 


   309 228 145
 - 81 - 83 - 85

  ---- ---- ---
   228 145 60


  Since you can not continue on (the last possible deduction 
from the balance - this is an extreme right), the last of the 
deductible numbers should be increased by 1, and then divide by 
2 to get the root. The last remnant and a remnant of the square 
root: 


  85 +1 = 86, 86 / 2 = 43,

  1909 = (43) ¤ +60.


  This algorithm is quite simple to program with long numbers, 
and it gives a reasonable computation time.


  You have many opportunities to represent
their dannye.Tak how we operate with chunks
two digits, then you can ask your
data tables of integers in the range
from 0 to 99.

  You may submit their integers
as strings of symbols, which are used
only numeric characters (numbers) from 0 to
9. The choice of method depends on your preferences and the 
capabilities of your machine to operate with the tables and 
chains. Carefully consider what actions need to be done. You 
are in no way limited to: why not programmed, and compare two 
different solutions?


  I offered you an algorithm without proof. So try to check it 
... 

  I offered you an algorithm for the decimal
number system. Can propose a similar algorithm for a binary 
system. Then does not arise cycle subtraction of consecutive 
odd numbers from each piece, as only one piece of an odd 
number: 1. Algorithm is simpler: if you can deduct

odd number - we subtract, otherwise do nothing. Then we shift, 
we add 1 and assign 1 at the end ... This algorithm is much 
simpler to implement. But then one must first go to the bottom 
2 and then convert the binary the result in decimal. You should 
see what is better ... " 


   Despite the bad translation and the lack of explanation 
"why", I mean, where should correct the algorithm, it is still 
obvious that the algorithm - ours. It is understood the same as 
that implemented above. That is, now We got him a verbal 
description of transcription in the number system with an 
arbitrary basis. 

   But we need just the binary case. (Unfavorable radix greater 
than 2 should be at least from the the fact that in an infinite 
basis of root extraction problem is reduced again to serial 
subtraction of odd numbers.) 


              Explanation.


   What is the essence of the method?

   Absolutely clear that the first digit on the left result, we 
can always get easily, using only two digits left of the 
initial number. 

   The method consists in the fact that we get the root "of the 
first four digits, using already gained root "of the first two

figures "and so on.

   Go directly to the binary case, we
can simplify the understanding.

   Imagine the real axis on which the marked segments of odd 
lengths, increasing from left to right, from the segments of 
which there are and "is" our original chislo.Pust the number N 
is not a perfect square, then it is on the axis of the right of 
the square root of q = [√ N], differing from it in a remnant of 
the square root. 

   You can also draw attention to the
fact that the latest addition is an odd
equal to 2q-1, and the next would 2q +1, but N
was too small for this. Therefore,
it is obvious that the remainder of the square root is not
than 2q.

   Suppose we learned that the previous
approximation of the root (ie the integral part of the square 
root of N / 4) is equal to r, and we need to get Another bit of 
the result, ie ascertain which is equal to q: 2r or 2r +1.


   We can find only one
comparison. If N is less than 4r ¤ +4 r +1
(Where 4r +1 - it "should be added
odd "to the square of the number 2r, it is" the last appended 
odd "to the square number 2r +1), then q = 2r, otherwise q = 2r 
+1. Logical? 


            Proof.


   Specially-headed fellow is quite satisfied with the enclosed 
proof:) 

Given N Є 0

            _
Find q = [√ N]

      0 ___

                  / N
Define q as √

          i 4 ^ i
(Square brackets - the integral part,
sign ^ - exponentiation)

Obviously, such a q must have the properties: i

          N
(E) q ¤ є

    i 4 ^ i

              N
(X) (q +1) ¤>

     i 4 ^ i

We denote imax number of pairs of bits in the binary 
representation of N. 

imax> log N

         4
Again, it is obvious that

          _____

         / N
q = √ = 0
4 ^ imax imax

Begin to carry out the proof by induction on i. Let it be known 
q (q is known) 

                        i imax
We prove that q, we obtain the following

             i-1
formula that satisfies the properties (e) and (g)
(Then q and a solution).

       0

                    i i-1

       2q, if N-4 q ¤ <(2 (2q) +1) · 4

         i i i
q =
i-1 2q +1 otherwise (Є ... ...)

         i


   Let us write these conditions again
as follows:

   top:

           i 1 i
(B) if the N-4 q ¤ <(q +) · 4

             i i 4

   bottom:

           i 1 i
(B) if the N-4 q ¤ Є (q +) · 4

             i i 4


   We prove the upper case.

                                      N
1. We prove (e) for q: q ¤ є

                    i-1 i-April 1 ^ (i-1)
that, using q = 2q, can be written in
a: i-1 i

         N N
4q ¤ є, ie q ¤ є,
 i 4 ^ (i-1) i 4 ^ i
that is known by (e) for q.

                                    i
2. We prove (x) for q, ie

                    i-1

              N
(Q +1) ¤>, ie
 i-April 1 ^ (i-1)

                  N
q ¤ +2 q +1>, ie (Using
i-1 i-April 1 ^ (i-1)
expression q = 2q):

            i-1 i

               N
4q ¤ +4 q +1>. Multiply by 4 ^ (i-1):
 i i 4 ^ (i-1)

i i i-1
4 q ¤ +4 q +4> N, ie:

  i i

  i i i-1
N-4 q ¤ <q · 4 +4

    i i
what is known on the condition (s).


   Now we prove the lower case.

                                      N
3. We prove (e) for q: q ¤ є

                    i-1 i-April 1 ^ (i-1)
that, using q = 2q +1, we can write
in the form of: i-1 i

               N
4q ¤ +4 q +1 €. Multiply by 4 ^ (i-1):
 i i 4 ^ (i-1)


  i i i-1
N-4 q ¤ Є q · 4 +4

    i i
that is known by (b).

4. We prove (x) for q, ie

                    i-1

              N
(Q +1) ¤>, ie (Using the expression i-January 4 ^ (i-1)
zheniem q = 2q +1):

        i-1 i

             N N
(2q +2) ¤>, ie (Q +1) ¤>,

  i 4 ^ (i-1) i 4 ^ i
which again is known by (x)
for q.

     i


   Thus the proof is complete. (Voices: "Something you can not 
prove anything, uncle! Where OUR SOMETHING algorithm?? ";))



           Getting to simplify!


                    i 1 i

       2q, if N-4 q ¤ <(q +) · 4

         i i i 4
q =
i-1 2q +1 otherwise (Є ... ...)

         i

                i
Denote M = N-4 q ¤. In particular, M = N.

           i i imax
Already obtain two formulas:

                          1 i

       2q, if M <(q +) · 4

         i i i 4
q =
i-1 2q +1 otherwise (Є ... ...)

         i

                         1 i

       M, if M <(q +) · 4

        i i i 4
M = 1, i
i-1 M - (q +) · 4 otherwise.

        i i 4


   Formula for M can be proved simply.

   Top:

        i-1 i-1 i
M = N-4 q ¤ = N-4 (2q) ¤ = N-4 q ¤
i-1 i-1 i i
that is a record for M.

                            i

   Lower:

        i-1 i-1
M = N-4 q ¤ = N-4 (2q +1) ¤ =
i-1 i-1 i

    i-1 i i i-1
= N-4 (4q ¤ +4 q +1) = N-4 q ¤ -4 q -4 =

          i i i i

     i i-i 1 January
= M -4 q -4 = M - (q +) · 4

  i i i i 4
QED.


                         1
Now let R = q +. Then q = [R].

                  4 i i i i

                       1
And, in particular, R =.

                 imax 4
Obtain the expressions:

              1 i

       2 [R] +, if M