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
