如何在 C 中使用链表进行大整数乘法运算？
how do I do big int multiplication using linked lists in C?
我正在接受字符串格式的输入。然后我将每个数字转换为整数，并将每个数字存储在链表节点中。我本可以使用数组，但我避免了，因为它们有内存限制并且是静态的。
请告诉我以下代码哪里出错了？
# include<stdio.h>
# include<stdlib.h>
# include<string.h>
struct ll{
int digit;
int place;
struct ll *next;
};
typedef struct ll node;
node *insert(node *head,int dig, int plac)//to insert new nodes{
if(head==NULL){
head=(node *)malloc(sizeof(node));
head->digit=dig;
head->place=plac;
head->next=NULL;
return head;
}
else{
head->next=insert(head->next,dig,plac);
return head;
}
}
void print(node *a)//to print all the nodes in the linked list{
node *temp;
temp=a;
while(temp!=NULL){
printf("%d\n",temp->digit);
temp=temp->next;
}
}
node *string_to_trainofdig(char h[],node *head){ //converting a string to integer digits and storing them individually in the linked list
int q,i;
q=strlen(h);int j;node *temp;temp=(node *)malloc(sizeof(node));
printf("value of q is %d\n",q);
for(i=q-1;i>=0;i--){
printf("value of i %d\n",i);
switch(h[i]){
case '0':j=0;break;
case '1':j=1;break;
case '2':j=2;break;
case '3':j=3;break;
case '4':j=4;break;
case '5':j=5;break;
case '6':j=6;break;
case '7':j=7;break;
case '8':j=8;break;
case '9':j=9;break;
}
printf("j is %d\n",j);
temp=insert(head,j,i);
head=temp;
}
return temp;
}
int count(node *q){ //counting the total number of nodes in a linked list
int p=0;;
node *w;
w=q;
while(w!=NULL){
p++;
w=w->next;
}
return p;
}
int pos(node *a, int y){ //this function returns the digit stored in a //particular node (specified by its position)
y--;
node *temp; temp=a;
if(a==NULL){
return 0;
}
else{
while(temp!=NULL || y!=0){
temp=temp->next;
y--;
}
if(temp==NULL){
return 0;
}
else if(y==0){
return temp->digit;
}
}
}
node *modify(node *a,int value,int posi){ /*inserts nodes and assigns them //values if empty (NULL) but modifies the value stored in that position in the //linked list if not NULL*/
node *temp; temp=a; posi--;
if(a==NULL){
return insert(a,value,posi);
}
else{
while(temp!=NULL || posi!=0){
temp=temp->next;
posi--;
}
if(temp==NULL){
return NULL;
}
else if(posi==0){
temp->digit=value;
}
return a;
}
}
char *mult(node *a,node *b){ //taking two linked lists as parameters and multiplying them
char e[1000000];
node *as; node *bs;
as=a;bs=b;
int z,x,m,n,v,r;
m=0; n=0;
node *newe;node *newe2;
char er[1000000];
newe=NULL;
int s;
s=count(a)>count(b)?count(a):count(b);
as=count(a)>count(b)?a:b;//determines which linked list is bigger and //assigns that to as
bs=count(a)>count(b)?b:a;//bs is smaller of the two linkedc lists
int fr=0;int ca=0; int i=0;
while(bs!=NULL)//main algorithm{
i=fr;//fr is initially 0
while(as!=NULL){
m=as->digit*bs->digit+m;//m is zero initially
n=m%10;
m=m/10;
ca=(pos(newe,i));// ca gets the value stored in the ith position of node //newe---->will be 0 initially since NULL
newe=modify(newe,n+ca,i);
as=as->next;i++;
}
as=count(a)>count(b)?a:b;
bs=bs->next;
fr++;//increments fr so that i comes back to fr
}
}
main(){
char d[1000]; char p[1000];
scanf("%s",d);
scanf("%s",p);
int q,w;
node *l,*u; l=NULL; u=NULL;
l=string_to_trainofdig(d,l);
u=string_to_trainofdig(p,u);
print(l);
print(u);
char *t;
t=mult(l,u);
printf("done\n");
}
如果您尝试对任意长整数进行整数数学运算，那么我建议您使用 GMP 库或类似库，而不是自己动手。
I could have used arrays, but avoided that because they have a memory limit and are static
这是不正确的。虽然您可以在 C 中将数组声明为静态块，但您可以根据需要轻松简单地声明一个指针和 malloc() space（当然要记住 free()）。
Please tell me where I am going wrong in the following code?
在发帖时，这种含糊不清的问题不是提问的方式。
您告诉 我们 发生了什么以及您期望什么，一些示例输入和输出或错误报告。
链接列表（特别是对于这种情况）性能极差。每次你跟随 link（例如 temp=temp->next;），这都是潜在的缓存未命中，并且会破坏现代（乱序）CPU 上的指令并行性，因为 [= 的新值14=]后面的代码所依赖的，要到后来才能知道。它们还倾向于将数据散布到各处（缓存局部性差），这使得前两个问题变得更糟，并使线性迭代 "un-prefetchable"（不像 "for each element in array"，其中 CPU 可以简单地检测模式和预取需要之前的数据）。
对于大整数，将整数存储为 "base 10" 也会产生极差的性能。这只是由于内存使用效率较低造成的（例如，在每个字节中存储一个 0 到 9 的值，而这些字节本来可以存储 0 到 255 的值）。主要问题是大多数更高级别的操作具有 "per digit" 开销（加法、减法、AND、OR）或 "per digit squared" 开销（乘法）。小基数（例如 "base 10"）意味着更多的数字，这意味着大量的开销。更大的基数（例如 "base 4294967296"）意味着更少的数字和更少的开销。除了使用 "power of 2" 大小允许您使用移位和掩码而不是模数和除法（例如 digit = temp%10; temp /= 10; 与 digit = temp & 0xFF; temp >>= 8;）；并使用 "whole integer" 尺寸使其更加高效 (digit = temp; temp >>= 32;)。基本上;要获得可接受的性能，您需要匹配 CPU 的原始大小 - 例如在 32 位系统上使用 "base 4294967296"，在 64 位系统上使用 "base 18446744073709551616"。
如果你将这两者结合起来，你可能会得到更像这样的东西：
typedef struct {
int current_digits;
int allocated_digits;
uint32_t digits[];
} BIG_INTEGER;
请注意，current_digits 和 allocated_digits 字段可让您避免一直调整数组大小。例如：
#define EXTRA_DIGITS 16
if(number->current_digits + 1 < number->allocated_digits) {
number->allocated_digits = number->current_digits + 1 + EXTRA_DIGITS;
newsize = sizeof(BIG_INTEGER) + sizeof(uint32_t)*number->allocated_digits;
number = realloc(number, newsize);
}
number->digits[number->current_digits] = 0;
number->current_digits++;
乘法本身；它大致是这样的（假设 32 位或 uint32_t 用于数字，根本没有测试）：
uint64_t temp; // Must be double the size of a digit
for(i = 0; i < number1->current_digits; i++) {
for(j = 0; j < number2->current_digits; j++) {
temp = number1->digits[i] * number2->digits[j];
k = i+j;
while(temp != 0) {
temp = temp + result->digits[k];
result->digits[k] = temp; // Lower half only
temp = temp >> 32;
k++;
}
}
}
您或许可以将其转换为使用 linked 列表而不是数组；但是...
我正在接受字符串格式的输入。然后我将每个数字转换为整数，并将每个数字存储在链表节点中。我本可以使用数组，但我避免了，因为它们有内存限制并且是静态的。 请告诉我以下代码哪里出错了？
# include<stdio.h>
# include<stdlib.h>
# include<string.h>
struct ll{
int digit;
int place;
struct ll *next;
};
typedef struct ll node;
node *insert(node *head,int dig, int plac)//to insert new nodes{
if(head==NULL){
head=(node *)malloc(sizeof(node));
head->digit=dig;
head->place=plac;
head->next=NULL;
return head;
}
else{
head->next=insert(head->next,dig,plac);
return head;
}
}
void print(node *a)//to print all the nodes in the linked list{
node *temp;
temp=a;
while(temp!=NULL){
printf("%d\n",temp->digit);
temp=temp->next;
}
}
node *string_to_trainofdig(char h[],node *head){ //converting a string to integer digits and storing them individually in the linked list
int q,i;
q=strlen(h);int j;node *temp;temp=(node *)malloc(sizeof(node));
printf("value of q is %d\n",q);
for(i=q-1;i>=0;i--){
printf("value of i %d\n",i);
switch(h[i]){
case '0':j=0;break;
case '1':j=1;break;
case '2':j=2;break;
case '3':j=3;break;
case '4':j=4;break;
case '5':j=5;break;
case '6':j=6;break;
case '7':j=7;break;
case '8':j=8;break;
case '9':j=9;break;
}
printf("j is %d\n",j);
temp=insert(head,j,i);
head=temp;
}
return temp;
}
int count(node *q){ //counting the total number of nodes in a linked list
int p=0;;
node *w;
w=q;
while(w!=NULL){
p++;
w=w->next;
}
return p;
}
int pos(node *a, int y){ //this function returns the digit stored in a //particular node (specified by its position)
y--;
node *temp; temp=a;
if(a==NULL){
return 0;
}
else{
while(temp!=NULL || y!=0){
temp=temp->next;
y--;
}
if(temp==NULL){
return 0;
}
else if(y==0){
return temp->digit;
}
}
}
node *modify(node *a,int value,int posi){ /*inserts nodes and assigns them //values if empty (NULL) but modifies the value stored in that position in the //linked list if not NULL*/
node *temp; temp=a; posi--;
if(a==NULL){
return insert(a,value,posi);
}
else{
while(temp!=NULL || posi!=0){
temp=temp->next;
posi--;
}
if(temp==NULL){
return NULL;
}
else if(posi==0){
temp->digit=value;
}
return a;
}
}
char *mult(node *a,node *b){ //taking two linked lists as parameters and multiplying them
char e[1000000];
node *as; node *bs;
as=a;bs=b;
int z,x,m,n,v,r;
m=0; n=0;
node *newe;node *newe2;
char er[1000000];
newe=NULL;
int s;
s=count(a)>count(b)?count(a):count(b);
as=count(a)>count(b)?a:b;//determines which linked list is bigger and //assigns that to as
bs=count(a)>count(b)?b:a;//bs is smaller of the two linkedc lists
int fr=0;int ca=0; int i=0;
while(bs!=NULL)//main algorithm{
i=fr;//fr is initially 0
while(as!=NULL){
m=as->digit*bs->digit+m;//m is zero initially
n=m%10;
m=m/10;
ca=(pos(newe,i));// ca gets the value stored in the ith position of node //newe---->will be 0 initially since NULL
newe=modify(newe,n+ca,i);
as=as->next;i++;
}
as=count(a)>count(b)?a:b;
bs=bs->next;
fr++;//increments fr so that i comes back to fr
}
}
main(){
char d[1000]; char p[1000];
scanf("%s",d);
scanf("%s",p);
int q,w;
node *l,*u; l=NULL; u=NULL;
l=string_to_trainofdig(d,l);
u=string_to_trainofdig(p,u);
print(l);
print(u);
char *t;
t=mult(l,u);
printf("done\n");
}
如果您尝试对任意长整数进行整数数学运算，那么我建议您使用 GMP 库或类似库，而不是自己动手。
I could have used arrays, but avoided that because they have a memory limit and are static
这是不正确的。虽然您可以在 C 中将数组声明为静态块，但您可以根据需要轻松简单地声明一个指针和 malloc() space（当然要记住 free()）。
Please tell me where I am going wrong in the following code?
在发帖时，这种含糊不清的问题不是提问的方式。
您告诉 我们 发生了什么以及您期望什么，一些示例输入和输出或错误报告。
链接列表（特别是对于这种情况）性能极差。每次你跟随 link（例如 temp=temp->next;），这都是潜在的缓存未命中，并且会破坏现代（乱序）CPU 上的指令并行性，因为 [= 的新值14=]后面的代码所依赖的，要到后来才能知道。它们还倾向于将数据散布到各处（缓存局部性差），这使得前两个问题变得更糟，并使线性迭代 "un-prefetchable"（不像 "for each element in array"，其中 CPU 可以简单地检测模式和预取需要之前的数据）。
对于大整数，将整数存储为 "base 10" 也会产生极差的性能。这只是由于内存使用效率较低造成的（例如，在每个字节中存储一个 0 到 9 的值，而这些字节本来可以存储 0 到 255 的值）。主要问题是大多数更高级别的操作具有 "per digit" 开销（加法、减法、AND、OR）或 "per digit squared" 开销（乘法）。小基数（例如 "base 10"）意味着更多的数字，这意味着大量的开销。更大的基数（例如 "base 4294967296"）意味着更少的数字和更少的开销。除了使用 "power of 2" 大小允许您使用移位和掩码而不是模数和除法（例如 digit = temp%10; temp /= 10; 与 digit = temp & 0xFF; temp >>= 8;）；并使用 "whole integer" 尺寸使其更加高效 (digit = temp; temp >>= 32;)。基本上;要获得可接受的性能，您需要匹配 CPU 的原始大小 - 例如在 32 位系统上使用 "base 4294967296"，在 64 位系统上使用 "base 18446744073709551616"。
如果你将这两者结合起来，你可能会得到更像这样的东西：
typedef struct {
int current_digits;
int allocated_digits;
uint32_t digits[];
} BIG_INTEGER;
请注意，current_digits 和 allocated_digits 字段可让您避免一直调整数组大小。例如：
#define EXTRA_DIGITS 16
if(number->current_digits + 1 < number->allocated_digits) {
number->allocated_digits = number->current_digits + 1 + EXTRA_DIGITS;
newsize = sizeof(BIG_INTEGER) + sizeof(uint32_t)*number->allocated_digits;
number = realloc(number, newsize);
}
number->digits[number->current_digits] = 0;
number->current_digits++;
乘法本身；它大致是这样的（假设 32 位或 uint32_t 用于数字，根本没有测试）：
uint64_t temp; // Must be double the size of a digit
for(i = 0; i < number1->current_digits; i++) {
for(j = 0; j < number2->current_digits; j++) {
temp = number1->digits[i] * number2->digits[j];
k = i+j;
while(temp != 0) {
temp = temp + result->digits[k];
result->digits[k] = temp; // Lower half only
temp = temp >> 32;
k++;
}
}
}
您或许可以将其转换为使用 linked 列表而不是数组；但是...