Sz\303\241m\303\255t\303\263g\303\251pes sz\303\241melm\303\251let J\303\241rai Antal Ezek a programok csak szeml\303\251ltet\303\251sre szolg\303\241lnak

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn

restart;

# # We fix a base. For demo purposes: # B:=10;

IiM1

`mod`:=modp;

SSVtb2RwRyUqcHJvdGVjdGVkRw==

# # Carry addition to long number s # cadd:=proc(s,c) local i,r,cc,x; global B; r:=[]; cc:=c; for i from 1 to nops(s) do x:=s[i]+cc mod B; cc:=(s[i]+cc-x)/B; r:=[op(r),x] od; [r,cc] end;

Zio2JEkic0c2IkkiY0dGJTYmSSJpR0YlSSJyR0YlSSNjY0dGJUkieEdGJUYlRiVDJj5GKTciPkYqRiY/KEYoIiIiRjEtSSVub3BzRyUqcHJvdGVjdGVkRzYjRiRJJXRydWVHRjRDJT5GKy1JJG1vZEdGJTYkLCYmRiQ2I0YoRjFGKkYxSSJCR0YlPkYqKiYsKEY9RjFGKkYxRishIiJGMUY/RkM+Rik3JC1JI29wR0Y0NiNGKUYrNyRGKUYqRiU2I0Y/RiU=

# # Carry subtraction from long number s # csub:=proc(s,c) local i,r,cc,x; global B; r:=[]; cc:=c; for i from 1 to nops(s) do x:=s[i]-cc mod B; cc:=-(s[i]-cc-x)/B; r:=[op(r),x] od; [r,cc] end;

Zio2JEkic0c2IkkiY0dGJTYmSSJpR0YlSSJyR0YlSSNjY0dGJUkieEdGJUYlRiVDJj5GKTciPkYqRiY/KEYoIiIiRjEtSSVub3BzRyUqcHJvdGVjdGVkRzYjRiRJJXRydWVHRjRDJT5GKy1JJG1vZEdGJTYkLCYmRiQ2I0YoRjFGKiEiIkkiQkdGJT5GKiwkKiYsKEY9RjFGKkY/RitGP0YxRkBGP0Y/PkYpNyQtSSNvcEdGNDYjRilGKzckRilGKkYlNiNGQEYl

ss:=convert(100,base,B); csub(ss,2);

NyUiIiFGIyIiIg==

NyQ3JSIiKSIiKiIiIUYm

# # Comparision of long numbers # cmp:=proc(s1,s2) local i; if nops(s1)>nops(s2) then RETURN(1) fi; if nops(s1)<nops(s2) then RETURN(-1) fi; for i from nops(s1) by -1 to 1 do if s1[i]>s2[i] then RETURN(1) fi; if s1[i]<s2[i] then RETURN(-1) fi; od; 0 end;

Zio2JEkjczFHNiJJI3MyR0YlNiNJImlHRiVGJUYlQyZAJDItSSVub3BzRyUqcHJvdGVjdGVkRzYjRiYtRi02I0YkLUknUkVUVVJOR0YuNiMiIiJAJDJGMEYsLUYzNiMhIiI/KEYoRjBGOkY1SSV0cnVlR0YuQyRAJDImRiZGJyZGJEYnRjJAJDJGQUZARjgiIiFGJUYlRiU=

s1:=convert(123,base,B); s2:=convert(321,base,B); cmp(s1,s2);

NyUiIiQiIiMiIiI=

NyUiIiIiIiMiIiQ=

ISIi

# # Addition with carry, n digit # addc:=proc(s1,s2,c,n) local i,r,cc,x; global B; r:=[]; cc:=c; for i from 1 to n do x:=s1[i]+s2[i]+cc mod B; cc:=(s1[i]+s2[i]+cc-x)/B; r:=[op(r),x] od; [r,cc]; end;

Zio2JkkjczFHNiJJI3MyR0YlSSJjR0YlSSJuR0YlNiZJImlHRiVJInJHRiVJI2NjR0YlSSJ4R0YlRiVGJUMmPkYrNyI+RixGJz8oRioiIiJGM0YoSSV0cnVlRyUqcHJvdGVjdGVkR0MlPkYtLUkkbW9kR0YlNiQsKCZGJDYjRipGMyZGJkY9RjNGLEYzSSJCR0YlPkYsKiYsKkY8RjNGPkYzRixGM0YtISIiRjNGP0ZDPkYrNyQtSSNvcEdGNTYjRitGLTckRitGLEYlNiNGP0Yl

addc(s,s1,2,3);

NyQ3JSwmJkkic0c2IjYjIiIiRikiIiZGKSwmJkYmNiMiIiNGKUYuRiksJiZGJjYjIiIkRilGKUYpIiIh

# # Subtraction with carry, n digit # subc:=proc(s1,s2,c,n) local i,r,cc,x; r:=[]; cc:=c; for i from 1 to n do x:=s1[i]-s2[i]-cc mod B; cc:=-(s1[i]-s2[i]-cc-x)/B; r:=[op(r),x] od; [r,cc] end;

Zio2JkkjczFHNiJJI3MyR0YlSSJjR0YlSSJuR0YlNiZJImlHRiVJInJHRiVJI2NjR0YlSSJ4R0YlRiVGJUMmPkYrNyI+RixGJz8oRioiIiJGM0YoSSV0cnVlRyUqcHJvdGVjdGVkR0MlPkYtLUkkbW9kR0YlNiQsKCZGJDYjRipGMyZGJkY9ISIiRixGP0kiQkdGJT5GLCwkKiYsKkY8RjNGPkY/RixGP0YtRj9GM0ZARj9GPz5GKzckLUkjb3BHRjU2I0YrRi03JEYrRixGJUYlRiU=

subc(s1,s2,2,3);

NyQ3JSIiIUYkIiIpIiIi

x:='x'; i:='i'; s1:=convert(123,base,B); p1:=add(s1[i]*x^(i-1),i=1..nops(s1)); s2:=convert(321,base,B); p2:=add(s2[i]*x^(i-1),i=1..nops(s2)); convert(123*321,base,B); expand(p1*p2); convert(1002003*3002001,base,B^3);

SSJ4RzYi

SSJpRzYi

NyUiIiQiIiMiIiI=

LCgiIiQiIiIqJiIiI0YkSSJ4RzYiRiRGJCokKUYnRiZGJEYk

NyUiIiIiIiMiIiQ=

LCgiIiJGIyomIiIjRiNJInhHNiJGI0YjKiYiIiRGIylGJkYlRiNGIw==

NyciIiQiIikiIiUiIipGIw==

LCwiIiQiIiIqJiIiKUYkSSJ4RzYiRiRGJComIiM5RiQpRiciIiNGJEYkKiZGJkYkKUYnRiNGJEYkKiZGI0YkKUYnIiIlRiRGJA==

NyciIiQiIikiIzlGJEYj

# # Single digit multiplication # mul11:=proc(x,y) global B; convert(x[1]*y[1],base,B); [%[1],%[2]] end;

Zio2JEkieEc2IkkieUdGJUYlRiVGJUMkLUkoY29udmVydEclKnByb3RlY3RlZEc2JSomJkYkNiMiIiJGLyZGJkYuRi9JJWJhc2VHRiVJIkJHRiU3JCZJIiVHRiVGLiZGNTYjIiIjRiU2I0YyRiU=

mul11([2],[7]);

NyQiIiUiIiI=

# # Karatsuba's method; x and y are lists of nonnegative # digits with lenght 2^n. # kara:=proc(x,y,n) local m0,m00,m01,m1,m10,m11,m2,m20,m21,f,x0,x1,y0,y1,z0,z1,c0,c1; if n=0 then RETURN(mul11(x,y)) fi; x0:=[x[1..2^(n-1)]]; x1:=[x[1+2^(n-1)..2^n]]; y0:=[y[1..2^(n-1)]]; y1:=[y[1+2^(n-1)..2^n]]; m0:=kara(x0,y0,n-1); m00:=[m0[1..2^(n-1)]]; m01:=[m0[1+2^(n-1)..2^n]]; m2:=kara(x1,y1,n-1); m20:=[m2[1..2^(n-1)]]; m21:=[m2[1+2^(n-1)..2^n]]; f:=true; if cmp(x1,x0,2^(n-1))>=0 then z0:=subc(x1,x0,0,2^(n-1))[1] else z0:=subc(x0,x1,0,2^(n-1))[1]; f:=not f; fi; if cmp(y1,y0,2^(n-1))>=0 then z1:=subc(y1,y0,0,2^(n-1))[1]; else z1:=subc(y0,y1,0,2^(n-1))[1]; f:=not f; fi; m1:=kara(z0,z1,n-1); m10:=[m1[1..2^(n-1)]]; m11:=[m1[1+2^(n-1)..2^n]]; z0:=addc(m01,m20,0,2^(n-1)); c0:=z0[2]; z1:=addc(z0[1],m00,0,2^(n-1)); c1:=c0+z1[2]; z0:=addc(z0[1],m21,c1,2^(n-1)); c0:=c0+z2[2]; m21:=cadd(z0[1],m21,c0,2^(n-1)); if f then z1:=subc(z1[1],m10,0,2^(n-1)); c1:=z1[2]; z0:=subc(z0[1],m11,c1,2^(n-1)); c0:=z0[2]; m21:=csub(m21[2],c2); else z1:=addc(z1[1],m10,0,2^(n-1)); c1:=z1[2]; z0:=addc(z0[1],m11,c1,2^(n-1)); c0:=z2[2]; cadd(m21[1],c0); fi; [op(m00),op(z1[1]),op(z0[1]),op(m21[1])] end;

Zio2JUkieEc2IkkieUdGJUkibkdGJTY0SSNtMEdGJUkkbTAwR0YlSSRtMDFHRiVJI20xR0YlSSRtMTBHRiVJJG0xMUdGJUkjbTJHRiVJJG0yMEdGJUkkbTIxR0YlSSJmR0YlSSN4MEdGJUkjeDFHRiVJI3kwR0YlSSN5MUdGJUkjejBHRiVJI3oxR0YlSSNjMEdGJUkjYzFHRiVGJUYlQzxAJC9GJyIiIS1JJ1JFVFVSTkclKnByb3RlY3RlZEc2Iy1JJm11bDExR0YlNiRGJEYmPkYzNyMmRiQ2IzsiIiIpIiIjLCZGJ0ZLRkshIiI+RjQ3IyZGJDYjOywmRktGS0ZMRkspRk1GJz5GNTcjJkYmRkk+RjY3IyZGJkZTPkYpLUkla2FyYUdGJTYlRjNGNUZOPkYqNyMmRilGST5GKzcjJkYpRlM+Ri8tRmluNiVGNEY2Rk4+RjA3IyZGL0ZJPkYxNyMmRi9GUz5GMkkldHJ1ZUdGQUAlMUY+LUkkY21wR0YlNiVGNEYzRkw+RjcmLUklc3ViY0dGJTYmRjRGM0Y+Rkw2I0ZLQyQ+RjcmLUZkcDYmRjNGNEY+RkxGZnA+RjI0RjJAJTFGPi1GX3A2JUY2RjVGTD5GOCYtRmRwNiZGNkY1Rj5GTEZmcEMkPkY4Ji1GZHA2JkY1RjZGPkZMRmZwRlxxPkYsLUZpbjYlRjdGOEZOPkYtNyMmRixGST5GLjcjJkYsRlM+RjctSSVhZGRjR0YlNiZGK0YwRj5GTD5GOSZGNzYjRk0+RjgtRmZyNiYmRjdGZnBGKkY+Rkw+RjosJkY5RksmRjhGanJGSz5GNy1GZnI2JkZec0YxRjpGTD5GOSwmRjlGSyZJI3oyR0YlRmpyRks+RjEtSSVjYWRkR0YlNiZGXnNGMUY5RkxAJUYyQyc+RjgtRmRwNiYmRjhGZnBGLUY+Rkw+RjpGYXM+RjctRmRwNiZGXnNGLkY6RkxGaHI+RjEtSSVjc3ViR0YlNiQmRjFGanJJI2MyR0YlQyc+RjgtRmZyRmF0RmN0PkY3LUZmckZmdD5GOUZncy1GW3Q2JCZGMUZmcEY5NyYtSSNvcEdGQTYjRiotRmh1NiNGYnQtRmh1NiNGXnMtRmh1NiNGZXVGJUYlRiU=

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn