在 C 中使用数组的大整数
Big integers using array in C
#include <stdio.h>
#include <math.h>
int main(void) {
int a[100], carry,i,j=0,length=0,temp,leftcarry=0,l,n;
clrscr();
scanf("%d",&n);
for(i=0;i<100;i++) a[i]=0;
for(i=1;i<=n;i++){
a[j]+=i;
while(a[j]>=10){
carry=a[j]%10;
if(a[j]>=pow(10,(j+1))){
if(leftcarry==0){
a[j]=a[j]/10;
j++;
a[j]+=carry;
if(j>length)length=j;
}
else{
for(l=j+1;l<=length;l++){
temp=a[l+1];
a[l+1]=a[l];
a[l+2]=temp;
}
a[j+1]=carry;
leftcarry=0;
length=length+1;
}
}
else{
a[j]=a[j]/10;
a[j-1]+=a[j];
a[j]=carry;
j--;
if(a[j]>=10) leftcarry=1;
}
}
j=length;
}
for(i=0;i<=length;i++){
printf("%d",a[i]);
}
return 0;
}
我想获得一些使用数组处理大整数的经验，所以我编写了这段代码来计算前 n 个自然数的总和。对于给定的数字 <45，我得到了正确答案。但是对于给定的数字> = 45，我得到的答案比正确答案少2。我想知道为什么会这样。我还想知道其他更简单的处理大整数的方法。谢谢你。
编辑：谢谢大家的回答。现在问题解决了。
实现简单。
（这一小格是为了保证进位的发生。）
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
//range of one cell represent : 00-99
#define Base 100
#define Width 2
#define PRN PRIu8
typedef struct _unums {
size_t size;
uint8_t *nums;
} UNums;
void UNums_init(UNums *num){
num->nums = malloc(sizeof(*num->nums));
num->nums[0] = 0;
num->size = 1;
}
void UNums_print(UNums *num){
size_t i = num->size;
int w = 0;
do{
--i;
printf("%0*" PRN, w, num->nums[i]);
if(!w) w = Width;
}while(i!=0);
}
void UNum_drop(UNums *num){
free(num->nums);
num->nums = NULL;
}
//num += n. (n + num->nums[0] <= UINT_MAX) to work properly.
void UNums_add1(UNums *num, unsigned n){
unsigned carry = n, wk;
size_t i;
for(i=0;i<num->size;++i){
wk = num->nums[i] + carry;
num->nums[i] = wk % Base;
carry = wk / Base;
}
while(carry){
num->size += 1;
num->nums = realloc(num->nums, num->size * sizeof(*num->nums));
num->nums[i++] = carry % Base;
carry /= Base;
}
}
int main(void){
UNums num;
unsigned i, n;
UNums_init(&num);
scanf("%u", &n);
for(i=1;i<=n;++i)
UNums_add1(&num, i);
UNums_print(&num);
UNum_drop(&num);
return 0;
}
我认为这行是错误的：
if(a[j]>=pow(10,(j+1))){
我不知道这是错误还是唯一的错误。
这表示 'If the j-placed digit is greater than or equal to 10^(j+1)'。
我认为进位测试只是'j位digit是否大于或等于10。
该数字的 'order' 由其位置标识。它有时被称为位值表示法！
就好像 'tens' 列中的 'digit' 可以上升到 99，千列中的 'digit' 可以上升到 999。我不认为那是你想要的。
{999,99,9} 不是十进制数！那应该是{9,9,9,9,9,9}。
正如其他人也建议的那样，我强烈建议您实施小端模式，其中最低有效数字位于数组的开头。
然后整个加载变得更容易，因为您不需要所有的改组代码来制作 space.
那么你实现的算法就变成了：
- 将 i 添加到单位（位于
a[0]）。
- 如果a[0]>9，溢出！获取 'excess' 并迭代地向上移动数字（在数组中向上）添加多余部分（除以 10）以寻找每一步的进一步溢出。
您应该跟踪数字的 'order'（a[i]!=0 的最大 i）以检测固定长度数组的溢出。
您的下一个挑战是编写函数 int add_small(int a[100],int d,int p){}。
将数字 d*10^p 添加到 a where 0<=d<=10 and 0
之后 int add_big(int a[100],int b[100]) 循环调用 add_small。
万一它有助于你的谷歌搜索（你还不知道）你在这里做的事情叫做 'binary coded decimal'。这是将基数 10 转换为计算机程序的一种非常自然的方式，但（实际上）不是处理大整数的非常有效的方式。
它被认为有点硬核，但你应该参考计算机编程艺术卷。 1 第 4.3.1 章 'The Classical Algorithms'。如果您不是计算机科学本科生，您可以忽略这一点。如果你是计算机科学专业的本科生，你必须立即去图书馆阅读它。
编辑：我刚刚查看了您的个人资料。 "CSE Undergraduate Student, First Year"。是图书馆。
编辑：如果您坚持异端大端实现，请提示！
- 设j=长度-1
- 设a[j]+=i（加法）
- 如果a[j]>=10除以10取余
- 取a[j]的余数
- 如果 j 为零，转到完全溢出！
- 否则，减少j，将第3步的除法结果加到a[j]中，再次返回第3步。
- 完成！
- 完全溢出：如果 j 达到零，则将所有内容打乱一个槽，增加长度并将步骤 3 中的下溢除法放入 a[0]，就像步骤 3 一样。
鉴于您的实施，您可能会多次完全下溢，因此需要一个循环。
我想说的是，您的程序中存在结构性错误，新手比有经验的程序员更常见。您只是想在一个循环中做太多事情。
分而治之！这就是我们解决计算问题的方式。
将您的功能分为一个普通的加法循环，然后是这个洗牌循环，将溢出的数字放在数字的末尾。
正如我一直指出的那样，如果您是小端字节序，事情会更简单！
这是我为重新实现该解决方案而编写的代码，使用 'litle-endian' 方法，其中 a[0] 包含个位数，a[1] 包含十位数等。
#include <stdio.h>
int main(void)
{
int a[100];
int length = 0;
int n;
if (scanf("%d", &n) != 1 || n < 0)
return 1;
for (int i = 0; i < 100; i++)
a[i] = 0;
for (int i = 1; i <= n; i++)
{
int carry = 0;
int number = i;
int j;
for (j = 0; carry > 0 || number > 0; j++)
{
int digit = number % 10;
number /= 10;
a[j] += digit + carry;
carry = 0;
if (a[j] >= 10)
{
a[j] -= 10;
carry = 1;
}
}
if (j > length)
length = j;
}
printf("%d ", n);
for (int i = length; i > 0; i--)
printf("%d", a[i-1]);
long l = n;
printf(" %ld\n", (l * (l + 1)) / 2);
return 0;
}
它的输出是输入值，从'big number'数组中打印出的一系列数字，以及公式直接计算的结果（因为∑x = n·(n+1)÷2 , 对于 1..n 中的 x)。我用这个脚本的变体测试了它：
$ for i in $(range 40 50); do bn <<< $i; done
'bn' is up to date.
40 820 820
41 861 861
42 903 903
43 946 946
44 990 990
45 1035 1035
46 1081 1081
47 1128 1128
48 1176 1176
49 1225 1225
50 1275 1275
$
然后更全面地使用此脚本的变体：
$ for i in $(random -n 10 100000 999999 | sort -n)
> do
> bn <<< $i
> done |
> awk '{ print; if ( != ) print "BUG: " " -- " " != " }'
291478 42479857981 42479857981
393029 77236093935 77236093935
396871 78753493756 78753493756
490344 120218864340 120218864340
577519 166764386440 166764386440
580196 168313989306 168313989306
640090 204857924095 204857924095
876878 384457951881 384457951881
892825 398568686725 398568686725
974712 475032228828 475032228828
$
我实际上使用了 1000 的重复而不是仅仅 10，并且范围向上移动了 10,000..99,999，然后是 100,000..999,999；在此之前，我用较低的范围和序号做了类似的证明。
并且我向上扩展了测试范围：
$ for i in $(random -n 10 1000000 9999999 | sort -n); do bn <<< $i; done | awk '{ print; if ( != ) print "BUG: " " -- " " != " }'
1291994 834624894015 834624894015
2032157 2064832052403 2064832052403
2266405 2568296945215 2568296945215
3187934 5081463188145 5081463188145
6045841 18276099721561 18276099721561
7248630 26271322062765 26271322062765
8604056 37014894127596 37014894127596
9095266 41361936353011 41361936353011
9533328 45442176144456 45442176144456
9543073 45535125913201 45535125913201
$ for i in $(random -n 10 10000000 99999999 | sort -n); do bn <<< $i; done | awk '{ print; if ( != ) print "BUG: " " -- " " != " }'
11451834 65572256707695 65572256707695
44931846 1009435414949781 1009435414949781
55847914 1559494776999655 1559494776999655
72229304 2608536214276860 2608536214276860
81242212 3300148545947578 3300148545947578
88702606 3934076199946921 3934076199946921
89386055 3994933458924540 3994933458924540
93246667 4347470499927778 4347470499927778
95651750 4574628686857125 4574628686857125
97417038 4745039695055241 4745039695055241
$
（是的，当我测试代码的早期版本时，我确实得到了一些损坏的输出。）
#include <stdio.h>
#include <math.h>
int main(void) {
int a[100], carry,i,j=0,length=0,temp,leftcarry=0,l,n;
clrscr();
scanf("%d",&n);
for(i=0;i<100;i++) a[i]=0;
for(i=1;i<=n;i++){
a[j]+=i;
while(a[j]>=10){
carry=a[j]%10;
if(a[j]>=pow(10,(j+1))){
if(leftcarry==0){
a[j]=a[j]/10;
j++;
a[j]+=carry;
if(j>length)length=j;
}
else{
for(l=j+1;l<=length;l++){
temp=a[l+1];
a[l+1]=a[l];
a[l+2]=temp;
}
a[j+1]=carry;
leftcarry=0;
length=length+1;
}
}
else{
a[j]=a[j]/10;
a[j-1]+=a[j];
a[j]=carry;
j--;
if(a[j]>=10) leftcarry=1;
}
}
j=length;
}
for(i=0;i<=length;i++){
printf("%d",a[i]);
}
return 0;
}
我想获得一些使用数组处理大整数的经验，所以我编写了这段代码来计算前 n 个自然数的总和。对于给定的数字 <45，我得到了正确答案。但是对于给定的数字> = 45，我得到的答案比正确答案少2。我想知道为什么会这样。我还想知道其他更简单的处理大整数的方法。谢谢你。
编辑：谢谢大家的回答。现在问题解决了。
实现简单。
（这一小格是为了保证进位的发生。）
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
//range of one cell represent : 00-99
#define Base 100
#define Width 2
#define PRN PRIu8
typedef struct _unums {
size_t size;
uint8_t *nums;
} UNums;
void UNums_init(UNums *num){
num->nums = malloc(sizeof(*num->nums));
num->nums[0] = 0;
num->size = 1;
}
void UNums_print(UNums *num){
size_t i = num->size;
int w = 0;
do{
--i;
printf("%0*" PRN, w, num->nums[i]);
if(!w) w = Width;
}while(i!=0);
}
void UNum_drop(UNums *num){
free(num->nums);
num->nums = NULL;
}
//num += n. (n + num->nums[0] <= UINT_MAX) to work properly.
void UNums_add1(UNums *num, unsigned n){
unsigned carry = n, wk;
size_t i;
for(i=0;i<num->size;++i){
wk = num->nums[i] + carry;
num->nums[i] = wk % Base;
carry = wk / Base;
}
while(carry){
num->size += 1;
num->nums = realloc(num->nums, num->size * sizeof(*num->nums));
num->nums[i++] = carry % Base;
carry /= Base;
}
}
int main(void){
UNums num;
unsigned i, n;
UNums_init(&num);
scanf("%u", &n);
for(i=1;i<=n;++i)
UNums_add1(&num, i);
UNums_print(&num);
UNum_drop(&num);
return 0;
}
我认为这行是错误的：
if(a[j]>=pow(10,(j+1))){
我不知道这是错误还是唯一的错误。
这表示 'If the j-placed digit is greater than or equal to 10^(j+1)'。
我认为进位测试只是'j位digit是否大于或等于10。
该数字的 'order' 由其位置标识。它有时被称为位值表示法！ 就好像 'tens' 列中的 'digit' 可以上升到 99，千列中的 'digit' 可以上升到 999。我不认为那是你想要的。
{999,99,9} 不是十进制数！那应该是{9,9,9,9,9,9}。
正如其他人也建议的那样，我强烈建议您实施小端模式，其中最低有效数字位于数组的开头。
然后整个加载变得更容易，因为您不需要所有的改组代码来制作 space.
那么你实现的算法就变成了：
- 将 i 添加到单位（位于
a[0]）。 - 如果a[0]>9，溢出！获取 'excess' 并迭代地向上移动数字（在数组中向上）添加多余部分（除以 10）以寻找每一步的进一步溢出。
您应该跟踪数字的 'order'（a[i]!=0 的最大 i）以检测固定长度数组的溢出。
您的下一个挑战是编写函数 int add_small(int a[100],int d,int p){}。
将数字 d*10^p 添加到 a where 0<=d<=10 and 0
之后 int add_big(int a[100],int b[100]) 循环调用 add_small。
万一它有助于你的谷歌搜索（你还不知道）你在这里做的事情叫做 'binary coded decimal'。这是将基数 10 转换为计算机程序的一种非常自然的方式，但（实际上）不是处理大整数的非常有效的方式。
它被认为有点硬核，但你应该参考计算机编程艺术卷。 1 第 4.3.1 章 'The Classical Algorithms'。如果您不是计算机科学本科生，您可以忽略这一点。如果你是计算机科学专业的本科生，你必须立即去图书馆阅读它。
编辑：我刚刚查看了您的个人资料。 "CSE Undergraduate Student, First Year"。是图书馆。
编辑：如果您坚持异端大端实现，请提示！
- 设j=长度-1
- 设a[j]+=i（加法）
- 如果a[j]>=10除以10取余
- 取a[j]的余数
- 如果 j 为零，转到完全溢出！
- 否则，减少j，将第3步的除法结果加到a[j]中，再次返回第3步。
- 完成！
- 完全溢出：如果 j 达到零，则将所有内容打乱一个槽，增加长度并将步骤 3 中的下溢除法放入 a[0]，就像步骤 3 一样。
鉴于您的实施，您可能会多次完全下溢，因此需要一个循环。
我想说的是，您的程序中存在结构性错误，新手比有经验的程序员更常见。您只是想在一个循环中做太多事情。 分而治之！这就是我们解决计算问题的方式。 将您的功能分为一个普通的加法循环，然后是这个洗牌循环，将溢出的数字放在数字的末尾。
正如我一直指出的那样，如果您是小端字节序，事情会更简单！
这是我为重新实现该解决方案而编写的代码，使用 'litle-endian' 方法，其中 a[0] 包含个位数，a[1] 包含十位数等。
#include <stdio.h>
int main(void)
{
int a[100];
int length = 0;
int n;
if (scanf("%d", &n) != 1 || n < 0)
return 1;
for (int i = 0; i < 100; i++)
a[i] = 0;
for (int i = 1; i <= n; i++)
{
int carry = 0;
int number = i;
int j;
for (j = 0; carry > 0 || number > 0; j++)
{
int digit = number % 10;
number /= 10;
a[j] += digit + carry;
carry = 0;
if (a[j] >= 10)
{
a[j] -= 10;
carry = 1;
}
}
if (j > length)
length = j;
}
printf("%d ", n);
for (int i = length; i > 0; i--)
printf("%d", a[i-1]);
long l = n;
printf(" %ld\n", (l * (l + 1)) / 2);
return 0;
}
它的输出是输入值，从'big number'数组中打印出的一系列数字，以及公式直接计算的结果（因为∑x = n·(n+1)÷2 , 对于 1..n 中的 x)。我用这个脚本的变体测试了它：
$ for i in $(range 40 50); do bn <<< $i; done
'bn' is up to date.
40 820 820
41 861 861
42 903 903
43 946 946
44 990 990
45 1035 1035
46 1081 1081
47 1128 1128
48 1176 1176
49 1225 1225
50 1275 1275
$
然后更全面地使用此脚本的变体：
$ for i in $(random -n 10 100000 999999 | sort -n)
> do
> bn <<< $i
> done |
> awk '{ print; if ( != ) print "BUG: " " -- " " != " }'
291478 42479857981 42479857981
393029 77236093935 77236093935
396871 78753493756 78753493756
490344 120218864340 120218864340
577519 166764386440 166764386440
580196 168313989306 168313989306
640090 204857924095 204857924095
876878 384457951881 384457951881
892825 398568686725 398568686725
974712 475032228828 475032228828
$
我实际上使用了 1000 的重复而不是仅仅 10，并且范围向上移动了 10,000..99,999，然后是 100,000..999,999；在此之前，我用较低的范围和序号做了类似的证明。
并且我向上扩展了测试范围：
$ for i in $(random -n 10 1000000 9999999 | sort -n); do bn <<< $i; done | awk '{ print; if ( != ) print "BUG: " " -- " " != " }'
1291994 834624894015 834624894015
2032157 2064832052403 2064832052403
2266405 2568296945215 2568296945215
3187934 5081463188145 5081463188145
6045841 18276099721561 18276099721561
7248630 26271322062765 26271322062765
8604056 37014894127596 37014894127596
9095266 41361936353011 41361936353011
9533328 45442176144456 45442176144456
9543073 45535125913201 45535125913201
$ for i in $(random -n 10 10000000 99999999 | sort -n); do bn <<< $i; done | awk '{ print; if ( != ) print "BUG: " " -- " " != " }'
11451834 65572256707695 65572256707695
44931846 1009435414949781 1009435414949781
55847914 1559494776999655 1559494776999655
72229304 2608536214276860 2608536214276860
81242212 3300148545947578 3300148545947578
88702606 3934076199946921 3934076199946921
89386055 3994933458924540 3994933458924540
93246667 4347470499927778 4347470499927778
95651750 4574628686857125 4574628686857125
97417038 4745039695055241 4745039695055241
$
（是的，当我测试代码的早期版本时，我确实得到了一些损坏的输出。）