 |
Development of
Algorithmic Constructions |
 |
Quadration
This is a recursiv multiplication for quadrats.
Rules:
An even number is devided by 2,
an odd number is either mod 4 = 3 then 1 is added or
mod 4 = 1 then 1 is reduced and you get an even number
The first and second Binomi formular is used to calculate the square of an odd number
(a+1)^2=a^2+2a+1 and (a-1)^2=a^2-2a+1
For the even number (2*a)^2 = 4*a^2
The quadrat of a is calculated by a recursiv call.
This quadration is a little bit fasten than the school multiplication. You need 1/3 additions compared to normal binary quadration .
Implementation in Mupad:
- a:=12345;
quadrierung:=proc (a, g)
begin
if a>1 then
if a mod 2 = 0 then
a:=a/2;
q:=4*quadrierung (a);
else
if a mod 4 = 1 then
a:=a-1;
q:=quadrierung (a)+2*a+1;
else
a:=a+1;
q:=quadrierung (a)-2*a+1;
end_if;
end_if;
else
return (1);
end_if;
end_proc;
print (a, a^2, quadrierung (a));
12345, 152399025, 152399025