Übungsaufgabe 1: Summen

Summe(n):=block([k,s],
  s: 0,
  for k from 1 thru n do
    s: s+k^2,
  s
)$

Summe(100);

sum(k^2,k,1,n);

nusum(k^2,k,1,n);

Übungsaufgabe 2: Fibonaccizahlen mit Divide-and-Conquer

showtime: true;

Fib3[0]: 0$
Fib3[1]: 1$
Fib3(n):=block([temp, fib],
  if not(integerp(Fib3[n])) then
    if evenp(n) then
      (fib: Fib3(n/2),
       temp: fib*(fib+2*Fib3(n/2-1)), 
       Fib3[n]: temp
      )
    else 
      Fib3[n]: Fib3((n+1)/2)^2+Fib3((n-1)/2)^2,
  Fib3[n]
)$

res1: Fib3(100000);

res2: fib(100000);

res1: Fib3(1000000)$

res2: fib(1000000)$

res2-res1;

Fib4[0]: 0$
Fib4[1]: 1$
Fib4[n]:=if evenp(n) then Fib4[n/2]*(Fib4[n/2]+2*Fib4[n/2-1])
else Fib4[(n+1)/2]^2+Fib4[(n-1)/2]^2$

res1: Fib4[100000];

res2: fib(100000);

res1: Fib4[1000000]$

res2: fib(1000000)$

res2-res1;

Modulo-Funktion

Mod(a,b):=block([t],
    t:a,
    while t>=b do t:t-b,
  t
)$

Mod(a,b):=
    [t:a,
    while t>=b do t:t-b,
  t];

Mod(1234567,1234);

mod(1234567,1234);

Euklidischer Algorithmus

ggT(a,b):=
  if a<b then ggT(b,a) else
  if b=0 then a else
  ggT(b,mod(a,b))
$

ggT(12345678,234);

gcd(12345678,234);

a:random(10^1000);
b:random(10^1000);

ggT(a,b);

Modulare Potenzen

powermod(a,n,p):=
  if n=0 then 1 else
  if evenp(n) then mod(powermod(a,n/2,p)^2,p) else
  mod(powermod(a,n-1,p)*a,p)$

powermod(2,5,25);

a:random(10^100);
n:random(10^100);
p:random(10^100);

powermod(a,n,p);

Erweiterter Euklidischer Algorithmus und modulare Inverse

EEA(x,y):=block([g,s1,t1,s,t,res],
  if x>y then res:EEA(y,x) else
  if mod(y,x)=0 then res:[x,1,0] else
    ([g,s1,t1]:EEA(mod(y,x),x),
     s:t1-s1*part(divide(y,x),1),
     t:s1,
     res:[g,s,t]),
  res  
)$

res:EEA(1234,56789);

load(gcdex)$

result:igcdex(1234,56789);

result[1]*1234+result[2]*56789;

EEA(12347394837*56784394830489,56784394830489);

modinv(e,p):=block([res],
    load(gcdex),
    res:igcdex(e,p),
    mod(res[1],p)
)$

modinv(1234,56789);mod(1234*31800,56789);

Chinesischer Restsatz

load(gcdex)$

chrem(llist,mlist):=block([k,j,m,i,mu,g,s,t],
  k:length(mlist),
  m:product(mlist[j],j,1,k),
  for i from 1 thru k do
    (
        mu[i]:m/mlist[i],
        [s[i],t[i],g]:igcdex(mu[i],mlist[i])
    ),
  mod(sum(llist[j]*s[j]*mu[j],j,1,k),m)
)$

chrem([2,3,1],[3,4,7]);

chinese([0,0,1],[2,3,5]);

Prüfzeichenverfahren

ISBNPruefziffer(liste):=mod(sum(k*liste[k],k,1,length(liste)),11)$

ISBNPruefziffer([3,5,4,0,2,9,8,9,4]);

EANPruefziffer(liste):=mod(-sum(liste[k],k,1,length(liste))-2*sum(liste[2*k],k,1,length(liste)/2),10)$

EANPruefziffer([9,7,8,3,5,4,0,2,9,8,9,4]);