c - Large number stored as vector more efficiently
问题描述
In my current implementation, I'm initializing char vectors with random numbers representing very large numbers that are more than 20.000 digits. Then I multiply and do operations with these vectors.
I don't know how to initialize them with (for example) base 2^64, so that I can avoid doing the operations digit by digit. I also need to return the numbers to base-10 to the way it was originally represented.
Here's the current implementation:
#include <stdio.h>
#include <stdlib.h>
unsigned int seed;
int newrandom() {
seed = (214013*seed+2531011);
return (seed>>13);
}
void LongNumInit( char *L, unsigned N )
{
for ( int i=0; i< N; i++ )
{
L[i] = newrandom() % 10;
}
}
void PrintNumber( char *L, unsigned N, char *Name )
{
printf("%s:", Name);
for ( int i=N; i>0; i-- )
{
printf("%d", L[i-1]);
}
printf("\n");
}
void ValueSet( char *L, unsigned N, char digit )
{
for ( int i=0; i< N; i++ )
{
L[i] = digit;
}
}
void CPNumber( char *Vin, char *Vout, unsigned N )
{
for ( int i=0; i< N; i++ )
{
Vout[i] = Vin[i];
}
}
char Add( char *Vin1, char *Vin2, char *Vout, unsigned N )
{
char CARRY = 0;
for ( int i=0; i< N; i++ )
{
char R = Vin1[i] + Vin2[i] + CARRY;
if ( R <= 9 )
{
Vout[i] = R; CARRY = 0;
}
else
{
Vout[i] = R-10; CARRY = 1;
}
}
return CARRY;
}
char DigitAddition( char *V, char digit, unsigned N )
{
int i=0;
char R = V[0] + digit;
if (R < 10)
{
V[0] = R; return 0;
}
V[0] = R-10;
char CARRY = 1;
i = 1;
while ( CARRY && i < N )
{
if ( V[i] < 9 )
{
V[i] = V[i] + 1; CARRY = 0;
}
else
{
V[i] = 0; i++;
}
}
return CARRY;
}
char AddInHorizontal( char *Vin, char *Vout, unsigned N )
{
char CARRY = 0;
ValueSet ( Vout, N, 0 );
for ( int i=0; i< N; i++ )
{
DigitAddition ( Vout, Vin[i], N );
}
return 0;
}
char MultiplyConst( char *V, unsigned N, char digit )
{
char CARRY = 0;
for ( int i=0; i< N; i++ )
{
char R = V[i] * digit + CARRY;
CARRY = R / 10;
R = R - CARRY*10;
V[i] = R;
}
return CARRY; // may be from 0 to 9
}
void Mult( char *Vin1, char *Vin2, char *VoutH, char *VoutL, unsigned N )
{
unsigned char *TEMP= (unsigned char*) malloc( 2*N*sizeof(unsigned char) );
unsigned char *RES = (unsigned char*) malloc( 2*N*sizeof(unsigned char) );
ValueSet ( RES, 2*N, 0 ); // Set RES to 0
for ( int i=0; i<N; i++ )
{
ValueSet ( TEMP, 2*N, 0 );
CPNumber ( Vin1, TEMP+i, N );
MultiplyConst( TEMP, 2*N, Vin2[i] );
Add ( TEMP, RES, RES, 2*N ); // TEMP + RES -> RES
}
CPNumber ( RES, VoutL, N );
CPNumber ( RES+N, VoutH, N );
}
int main (int argc, char **argv)
{
int i, sum1, sum2, sum3, N=10000;
seed = 12345;
if (argc>1) { N = atoi(argv[1]); }
if (argc>2) { Rep = atoi(argv[2]); }
unsigned char *V1= (unsigned char*) malloc( N*sizeof(unsigned char) );
unsigned char *V2= (unsigned char*) malloc( N*sizeof(unsigned char) );
unsigned char *V3= (unsigned char*) malloc( N*sizeof(unsigned char) );
unsigned char *V4= (unsigned char*) malloc( N*sizeof(unsigned char) );
LongNumInit ( V1, N );
LongNumInit ( V2, N );
LongNumInit ( V3, N );
Add ( V1, V2, V4, N );
Mult ( V3, V4, V2, V1, N );
AddInHorizontal ( V1, V2, N );
DigitAddition ( V3, V2[0], N );
PrintNumber( V1, 32, "V1" );
PrintNumber( V2, 32, "V2" );
PrintNumber( V3, 32, "V3" );
PrintNumber( V4, 32, "V4" );
free(V1);
free(V2);
free(V3);
free(V4);
return 0;
}
解决方案
推荐阅读
- python - Pandas 根据日期范围和另一列过滤数据框
- html - 从 React 中的隐藏溢出中弹出
- facebook-graph-api - 获取给定日期的 Instagram 关注者数量
- r - 为什么 r 中关于生成 Gamma 随机变量的代码不返回预期的输出?
- cross-browser - 我应该如何做跨浏览器解决方案?
- powershell - 如何使用 powershell 传递参数?
- python - Python 类 - 存储和引用实例
- python - 如何在两个不同的 Github 存储库中同步一些文件夹?
- oop - 实现相同接口的不同类进入构造函数
- python - 具有重叠部分的图像的字符分割