Таблиця 1. Варіанти представлення числа
#include<stdio.h>
#include<math.h>
#define MaxDig 4
#define n_Osn 4
void input(long a[MaxDig]);
void output(long a[MaxDig]);
void sum(long a[MaxDig], long b[MaxDig], long c[MaxDig]);
int eq(long a[MaxDig], long b[MaxDig]);
int less(long a[MaxDig], long b[MaxDig]);
int less_eq(long a[MaxDig], long b[MaxDig]);
void main()
{
long a[MaxDig];
long b[MaxDig];
long c[MaxDig];
printf("Enter the first number: ");
input(a);
printf("Enter the second number: ");
input(b);
sum(a,b,c);
printf("sum=");
output(c);
printf("less_eq=%d",less_eq(a,b));
}
void input(long a[MaxDig])
{
long Osn,i,ch;
char c[1];
Osn=pow(10,n_Osn);
for(i=0;i<MaxDig;i++)
a[i]=0;
a[0]=1;
while((c[0]=getch())!=13)
{
ch=atoi(c);
printf("%c",c[0]);
for(i=MaxDig-a[0];i<MaxDig;i++)
{
a[i-1]=a[i-1]+a[i]*10/Osn;
a[i]=a[i]*10%Osn;
}
a[MaxDig-1]+=ch;
if((a[MaxDig-1-a[0]]>0)&&(MaxDig-1-a[0]!=0)) a[0]++;
if((a[1]/(Osn/10))>0) break;
}
printf("\n");
}
void output(long a[MaxDig])
{
int i,j,NN,Osn,p;
long N;
Osn=pow(10,n_Osn);
printf("%ld",a[MaxDig-a[0]]);
for(i=MaxDig-a[0]+1;i<MaxDig;i++)
{
N=a[i];
if(N==0) NN=0;
for(p=0;N>0;p++)
{
N/=10;
}
while((n_Osn-p)!=0)
{
printf("0");
p++;
}
if(NN==1) printf("%ld",a[i]);
NN=1;
}
printf("\n");
}
void sum(long a[MaxDig], long b[MaxDig], long c[MaxDig])
{
int i,k,Osn=pow(10,n_Osn);
for(i=0;i<MaxDig;i++)
c[i]=0;
c[0]=1;
if(a[0]>b[0])
k=a[0];
else k=b[0];
for(i=MaxDig-1;i>MaxDig-k-1;i--)
{
c[i-1]=(c[i]+a[i]+b[i])/Osn;
c[i]=(c[i]+a[i]+b[i])%Osn;
}
if(c[MaxDig-k-1]==1) c[0]=k+1;
else c[0]=k;
}
int eq(long a[MaxDig], long b[MaxDig])
{
int e;
int i;
e=0;
if(a[0]!=b[0]) return e;
for(i=MaxDig-1;(i>=MaxDig-a[0])&&(a[i]==b[i]);i--)
e=(i==(MaxDig-a[0]));
return e;
}
int less(long a[MaxDig], long b[MaxDig])
{
int e=0,i;
if(a[0]<b[0]) e=1;
else e=0;
for(i=MaxDig-a[0];i<MaxDig;i++)
if(a[i]!=b[i])
if(a[i]<b[i]) e=1;
else e=0;
return e;
}
int less_eq(long a[MaxDig], long b[MaxDig])
{
int e=0;
if(less(a,b)||eq(a,b)) return 1;
return e;
}
#include<stdio.h>
#include<math.h>
#define MaxDig 4
#define N_Osn 4
void input(long a[MaxDig],char *str);
void output(long a[MaxDig]);
int more(long a[MaxDig], long b[MaxDig]);
void sub(long a[MaxDig], long b[MaxDig], long c[MaxDig]);
void copy(long a[MaxDig], long b[MaxDig]);
int eq(long a[MaxDig], long b[MaxDig]);
int not_eq(long a[MaxDig], long b[MaxDig]);
void main()
{
long a[MaxDig];
long b[MaxDig];
long c[MaxDig];
char *str1="number1.txt";
char *str2="number2.txt";
printf("a=");
input(a,str1);
printf("b=");
input(b,str2);
printf("\na-b=");
sub(a,b,c);
printf("\nnot_eq=%d",not_eq(a,b));
}
void input(long a[MaxDig],char *str)
{
int i,ch; long Osn;
char c[1];
FILE *fp;
fp=fopen(str,"r");
Osn=pow(10,N_Osn);
for(i=0;i<MaxDig;i++)
a[i]=0;
a[0]=1;
while((c[0]=getc(fp))!=EOF)
{
ch=atoi(c);
printf("%c",c[0]);
if((a[MaxDig-1]*10/Osn)>0)
{
a[0]=a[0]+1;
if(a[0]==MaxDig) { a[0]--; break; }
for(i=MaxDig-a[0];i<MaxDig-1;i++)
{
a[i]=a[i]+a[i+1]*10%Osn;
a[i+1]=a[i+1]*10/Osn;
}
}
else
{
a[MaxDig-1]=a[MaxDig-1]*10%Osn;
for(i=MaxDig-1;i>MaxDig-a[0];i--)
{
a[i]=a[i]+a[i-1]*10/Osn;
a[i-1]=a[i-1]*10%Osn;
}
}
a[MaxDig-a[0]]=a[MaxDig-a[0]]+ch;
}
printf("\n");
fclose(fp);
}
void output(long a[MaxDig])
{
int i,p;
int NN=1;
long N;
printf("%ld",a[MaxDig-1]);
for(i=MaxDig-2;i>=MaxDig-a[0];i--)
{
N=a[i];
if(N==0) NN=0;
for(p=0;N>0;p++)
N=N/10;
while((N_Osn-p)!=0)
{
printf("0");
p++;
}
if(NN==1) printf("%ld",a[i]);
NN=1;
}
}
int more(long a[MaxDig], long b[MaxDig])
{
int i;
if(a[0]>b[0]) return 1;
else if(a[0]<b[0]) return 0;
else
for(i=MaxDig-1;i>=MaxDig-a[0];i--)
if(a[i]>b[i]) return 1;
else if(a[i]<b[i]) return 0;
return 0;
}
void copy(long a[MaxDig], long b[MaxDig])
{
int i;
for(i=0;i<MaxDig;i++)
b[i]=a[i];
}
int eq(long a[MaxDig], long b[MaxDig])
{
int i,e=0;
if(a[0]==b[0])
{
for(i=MaxDig-1;(i>=MaxDig-a[0])&&(a[i]==b[i]);i--)
e=(i==MaxDig-a[0]);
}
else return 0;
return e;
}
void sub(long a[MaxDig], long b[MaxDig], long c[MaxDig])
{
int i,j,t;
long Osn;
long c1[MaxDig];
long c2[MaxDig];
int minus=0;
for(i=0;i<MaxDig;i++)
{
c1[i]=0;
c2[i]=0;
c[i]=0;
}
Osn=pow(10,N_Osn);
if(more(a,b))
{
copy(a,c1);
copy(b,c2);
minus=0;
}
else if(eq(a,b))
{
c[0]=1;
c[MaxDig-1]=0;
}
else
{
copy(b,c1);
copy(a,c2);
minus=1;
}
if(c1[0]>c2[0])
{
t=c1[0]-c2[0];
do
{
for(i=0;(MaxDig-c1[0]+i+1)<MaxDig;i++)
{
c2[MaxDig-c1[0]+i]=c2[MaxDig-c1[0]+i+1];
c2[MaxDig-c1[0]+i+1]=0;
}
t--;
}
while(t>0);
}
for(i=MaxDig-c1[0];i<MaxDig-c1[0]+c2[0];i++)
{
c1[i]=c1[i]-(int)c2[i];
j=i;
while((c1[j]<0)&&(j<=c1[0]))
{
c1[j]=c1[j]+Osn;
c1[j+1]=c1[j+1]-1;
j=j+1;
}
}
t=c1[0];
for(i=MaxDig-1;(c1[0]>0)&&(c1[i]==0);i--)
c1[0]=c1[0]-1;
for(i=t;t>c1[0];t--)
{
for(j=MaxDig-1;j>MaxDig-t;j--)
c1[j]=c1[j-1];
c1[j]=0;
}
copy(c1,c);
if(minus) printf("-");
output(c);
}
int not_eq(long a[MaxDig], long b[MaxDig])
{
if (eq(a,b)) return 0;
return 1;
}
#include<stdio.h>
#include<math.h>
#define MaxDig 4
#define N_Osn 4
#define Pi 3.141592653589793
long round(double x);
void input(long a[MaxDig]);
void output(long a[MaxDig]);
void fft(long a[MaxDig], double y[MaxDig*2][2], int N);
void mult_fft(long a[MaxDig], long b[MaxDig], long c[MaxDig*2]);
void scal_mult(double y1[MaxDig*2][2], double y2[MaxDig*2][2], double y[MaxDig*2][2]);
void transf(long c[MaxDig*2]);
void bfft(double y[MaxDig*2][2], long c[MaxDig*2], int N);
void main()
{
long a[MaxDig]={3,1230,4231,1233};
long b[MaxDig]={3,7001,1224,5124};
long c[MaxDig*2];
int i;
//input(a);
output(a);
//input(b);
output(b);
mult_fft(a,b,c);
output(c);
}
void input(long a[MaxDig])
{
int i,ch,Osn;
char c[1];
Osn=pow(10,N_Osn);
for(i=0;i<MaxDig;i++)
a[i]=0;
a[0]=1;
while((c[0]=getch())!=13)
{
ch=atoi(c);
if((a[1]*10/Osn)>0)
{
a[0]=a[0]+1;
if(a[0]==MaxDig) {a[0]--; break;}
for(i=a[0];i>1;i--)
{
a[i]=a[i]+a[i-1]*10%Osn;
a[i-1]=a[i-1]*10/Osn;
}
}
else
{
a[1]=a[1]*10%Osn;
for(i=1;i<a[0];i++)
{
a[i]=a[i]+a[i+1]*10/Osn;
a[i+1]=a[i+1]*10%Osn;
}
}
printf("%c",c[0]);
a[a[0]]=a[a[0]]+ch;
}
printf("\n");
}
void output(long a[MaxDig])
{
int i=0,p,NN=1;
long N;
printf("%ld",a[1]);
for(i=2;i<=a[0];i++)
{
N=a[i];
if(N==0) NN=0;
for(p=0;N>0;p++)
N=N/10;
while((N_Osn-p)!=0)
{
printf("%d",0);
p++;
}
if(NN==1) printf("%ld",a[i]);
NN=1;
}
printf("\n");
}
void fft(long a[MaxDig], double y[MaxDig*2][2], int N)
{
int i,j,k;
for(i=0;i<MaxDig*2;i++)
for(j=0;j<2;j++)
y[i][j]=0;
for(j=0;j<N;j++)
{
for(i=0;i<a[0];i++)
{
y[j][0]=y[j][0]+a[a[0]-i]*cos(2*Pi*i*j/N);
y[j][1]=y[j][1]+a[a[0]-i]*sin(2*Pi*i*j/N);
}
}
}
long round(double x)
{
if(x>=0)
return ((long)(x+0.5));
else
return ((long)(x-0.5));
}
void bfft(double y[MaxDig*2][2], long c[MaxDig*2], int N)
{
int i,j;
double t=0;
for(i=0;i<MaxDig*2;i++)
c[i]=0;
for(j=0;j<N;j++)
{
for(i=0;i<N;i++)
{
t=t+(y[i][0]*cos(2*Pi*i*j/N)-y[i][1]*sin(-2*Pi*i*j/N));
}
c[j]=round(t/N);
t=0;
}
}
void mult_fft(long a[MaxDig], long b[MaxDig], long c[MaxDig*2])
{
double y1[MaxDig*2][2];
double y2[MaxDig*2][2];
double y[MaxDig*2][2];
int i;
int N;
i=1;
do
{
N=pow(2,i);
i++;
}
while((a[0]+b[0])>N);
fft(a,y1,N);
fft(b,y2,N);
scal_mult(y1,y2,y);
bfft(y,c,N);
for(i=0;i<MaxDig*2;i++)
printf("%ld ",c[i]);
printf("\n");
transf(c);
}
void scal_mult(double y1[MaxDig*2][2], double y2[MaxDig*2][2], double y[MaxDig*2][2])
{
int i,j;
long t;
for(i=0;i<MaxDig;i++)
for(j=0;j<2;j++)
y[i][j]=0;
for(i=0;i<MaxDig*2;i++)
{
y[i][0]=y1[i][0]*y2[i][0]-y1[i][1]*y2[i][1];
y[i][1]=y1[i][0]*y2[i][1]+y1[i][1]*y2[i][0];
}
}
void transf(long c[MaxDig*2])
{
int i,j;
long t,Osn;
Osn=pow(10,N_Osn);
for(i=0;i<MaxDig*2-1;i++)
{
t=c[i]/Osn;
c[i+1]=c[i+1]+t;
c[i]=c[i]-t*Osn;
}
j=0;
for(i=MaxDig*2-1;(i>=0)&&(c[i]==0);i--) j++;
j=MaxDig*2-j;
for(i=j;i>=round(j*1.0/2);i--)
{
t=c[i];
c[i]=c[j-i];
c[j-i]=t;
}
c[0]=j;
}
#include<stdio.h>
#include<math.h>
#define MaxDig 4
#define N_Osn 4
void input(long a[MaxDig],char *str);
void output(long a[MaxDig]);
int more(long a[MaxDig], long b[MaxDig]);
void sub_zs(long a[MaxDig], long b[MaxDig], long c[MaxDig], int z);
void copy(long a[MaxDig], long b[MaxDig]);
int eq(long a[MaxDig], long b[MaxDig]);
int less(long a[MaxDig], long b[MaxDig]);
void mult_long_short(long a[MaxDig], long b, long c[MaxDig]);
void div_long(long a[MaxDig], long b[MaxDig], long res[MaxDig], long ost[MaxDig]);
long numb_div2(long ost[MaxDig], long b[MaxDig], int z);
int more_zs(long a[MaxDig], long b[MaxDig], int z);
int less_zs(long a[MaxDig], long b[MaxDig], int z);
void main()
{
long a[MaxDig];
long b[MaxDig];
long ost[MaxDig];
long res[MaxDig];
char *str1="number1.txt";
char *str2="number2.txt";
printf("a=");
input(a,str1);
printf("b=");
input(b,str2);
div_long(a,b,res,ost);
printf("res=");
output(res);
printf("ost=");
output(ost);
}
void input(long a[MaxDig],char *str)
{
int i,ch; long Osn;
char c[1];
FILE *fp;
fp=fopen(str,"r");
Osn=pow(10,N_Osn);
for(i=0;i<MaxDig;i++)
a[i]=0;
a[0]=1;
while((c[0]=getc(fp))!=EOF)
{
ch=atoi(c);
if((a[MaxDig-1]*10/Osn)>0)
{
a[0]=a[0]+1;
if(a[0]==MaxDig) { a[0]--; break; }
for(i=MaxDig-a[0];i<MaxDig-1;i++)
{
a[i]=a[i]+a[i+1]*10%Osn;
a[i+1]=a[i+1]*10/Osn;
}
}
else
{
a[MaxDig-1]=a[MaxDig-1]*10%Osn;
for(i=MaxDig-1;i>MaxDig-a[0];i--)
{
a[i]=a[i]+a[i-1]*10/Osn;
a[i-1]=a[i-1]*10%Osn;
}
}
printf("%c",c[0]);
a[MaxDig-a[0]]=a[MaxDig-a[0]]+ch;
}
printf("\n");
fclose(fp);
}
void output(long a[MaxDig])
{
int i,p;
int NN=1;
long N;
printf("%ld",a[MaxDig-1]);
for(i=MaxDig-2;i>=MaxDig-a[0];i--)
{
N=a[i];
if(N==0) NN=0;
for(p=0;N>0;p++)
N=N/10;
while((N_Osn-p)!=0)
{
printf("0");
p++;
}
if(NN==1) printf("%ld",a[i]);
NN=1;
}
printf("\n");
}
int more(long a[MaxDig], long b[MaxDig])
{
int i;
if(a[0]>b[0]) return 1;
else if(a[0]<b[0]) return 0;
else
for(i=MaxDig-1;i>=MaxDig-a[0];i--)
{
if(a[i]>b[i]) return 1;
else if(a[i]<b[i]) return 0;
}
return 0;
}
int more_zs(long a[MaxDig], long b[MaxDig], int z)
{
int i;
long Osn;
long b1[MaxDig];
Osn=pow(10,N_Osn);
copy(b,b1);
for(i=0;i<z;i++)
mult_long_short(b,Osn,b1);
return more(a,b1);
}
void copy(long a[MaxDig], long b[MaxDig])
{
int i;
for(i=0;i<MaxDig;i++)
b[i]=a[i];
}
int eq(long a[MaxDig], long b[MaxDig])
{
int i,e=0;
if(a[0]==b[0])
{
for(i=MaxDig-1;(i>=MaxDig-a[0])&&(a[i]==b[i]);i--)
e=(i==MaxDig-a[0]);
}
else return 0;
return e;
}
void mult_long_short(long a[MaxDig], long b, long c[MaxDig])
{
int i,j=0;
long t=0,Osn;
Osn=pow(10,N_Osn);
for(i=0;i<MaxDig;i++)
c[i]=0;
c[0]=1;
if(b!=0)
{
for(i=MaxDig-a[0];i<MaxDig;i++)
{
c[i]=(a[i]*b+t)%Osn;
t=(a[i]*b+t)/Osn;
}
while(t>0)
{
for(i=2;i<MaxDig;i++)
c[i-1]=c[i];
c[MaxDig-1]=t%Osn;
t=t/Osn;
j++;
}
c[0]=a[0]+j;
}
}
void sub_zs(long a[MaxDig], long b[MaxDig], long c[MaxDig], int z)
{
int i,j,t;
long Osn;
long c1[MaxDig];
long c2[MaxDig];
long b1[MaxDig];
int minus=0;
for(i=0;i<MaxDig;i++)
{
c1[i]=0;
c2[i]=0;
}
Osn=pow(10,N_Osn);
copy(b,b1);
for(i=0;i<z;i++)
mult_long_short(b,Osn,b1);
if(more(a,b1))
{
copy(a,c1);
copy(b1,c2);
minus=0;
}
else if(eq(a,b1))
{
c[0]=1;
c[MaxDig-1]=0;
}
else
{
copy(b1,c1);
copy(a,c2);
minus=1;
}
if(c1[0]>c2[0])
{
t=c1[0]-c2[0];
do
{
for(i=0;(MaxDig-c1[0]+i+1)<MaxDig;i++)
{
c2[MaxDig-c1[0]+i]=c2[MaxDig-c1[0]+i+1];
c2[MaxDig-c1[0]+i+1]=0;
}
t--;
}
while(t>0);
}
for(i=MaxDig-c1[0];i<MaxDig-c1[0]+c2[0];i++)
{
c1[i]=c1[i]-(int)c2[i];
j=i;
while((c1[j]<0)&&(j<=c1[0]))
{
c1[j]=c1[j]+Osn;
c1[j+1]=c1[j+1]-1;
j=j+1;
}
}
t=c1[0];
for(i=MaxDig-1;(c1[0]>0)&&(c1[i]==0);i--)
c1[0]=c1[0]-1;
for(i=t;t>c1[0];t--)
{
for(j=MaxDig-1;j>MaxDig-t;j--)
c1[j]=c1[j-1];
c1[j]=0;
}
copy(c1,c);
}
int less(long a[MaxDig], long b[MaxDig])
{
if (more(a,b)||eq(a,b)) return 0;
return 1;
}
int less_zs(long a[MaxDig], long b[MaxDig], int z)
{
int i;
long Osn;
long b1[MaxDig];
Osn=pow(10,N_Osn);
copy(b,b1);
for(i=0;i<z;i++)
mult_long_short(b,Osn,b1);
return less(a,b1);
}
void div_long(long a[MaxDig], long b[MaxDig], long res[MaxDig], long ost[MaxDig])
{
int i,zs;
long Osn;
long d[MaxDig];
long d1[MaxDig];
Osn=pow(10,N_Osn);
for(i=0;i<MaxDig;i++)
{
res[i]=0;
ost[i]=0;
d[i]=0;
}
res[0]=1;
ost[0]=1;
if(!eq(a,b))
{
if(!less(a,b))
{
copy(a,ost);
zs=a[0]-b[0];
mult_long_short(b,Osn,d);
copy(d,d1);
for(i=0;i<zs-1;i++)
{
copy(d,d1);
mult_long_short(d1,Osn,d);
}
if(less(a,d)) if(zs>0) zs--;
res[0]=zs+1;
for(i=zs;zs>=0;zs--)
{
res[MaxDig-(i-zs)-1]=numb_div2(ost,b,zs);
}
}
else
copy(a,ost);
}
else
res[1]=1;
}
long numb_div2(long ost[MaxDig], long b[MaxDig],int z)
{
int i;
long down=0,up;
long Osn;
long c[MaxDig];
for(i=0;i<MaxDig;i++)
c[i]=0;
Osn=pow(10,N_Osn);
up=Osn;
while((up-1)>down)
{
mult_long_short(b,(up+down)/2,c);
if(more_zs(ost,c,z)) down=(down+up)/2;
else if(less_zs(ost,c,z)) up=(down+up)/2;
else
{
up=(down+up)/2;
down=up;
}
}
mult_long_short(b,(up+down)/2,c);
if(more(ost,c)) sub_zs(ost,c,ost,z);
else
{
sub_zs(c,ost,c,z);
copy(c,ost);
}
return (down+up)/2;
}