C: multiplying big integers

[danbaron]

I made a program to multiply big integers in C.

It just uses plain C, nothing added to fix C's string handling.

As a test, I used two numbers that I calculated in Racket.

num1 = 386^387 (1002 digits)
num2 = 297^405 (1002 digits)

I calculated their product.

num3 = num1 * num2 (2003 digits)

The program multiplies just the way you would do it with a pencil and paper. I think that way is the simplest to implement. I think there are much faster ways, which are more complicated to implement.

Both Racket and the C program gave the same answer.

The difference is in the time of execution.

For Racket, the time was 0 - not even one millisecond.

For the C program, the time was 0.192 seconds. (But, this was just using Pelles C. Probably, it would run substantially faster if compiled with GCC.)

:( :o



' code --------------------------------------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <time.h>

#define maxdigits 50000

//-------------------------------------------------------------------------------------------------------

char* makechararray(int nchars);
int chararraylength(char* chararray);
void copymemory(char* from, char* to);
void changechararray(char* change, char* tothis);
char intval(char c);
char charval(char c);
void zeroreg(char* reg);
bool iszeroreg(char* reg);
void reversereg(char* reg);
void shiftregright(char* reg, int nplaces);
void multregbydigit(char* multreg, char* productreg, char cdigit);
void addregs(char* reg1, char* reg2, char* sumreg);
void multiplynums(char* n1, char* n2, char* productnum);
void reversecopynumtoreg(char* num, char* reg);
void reversecopyregtonum(char* reg, char* num);

//-------------------------------------------------------------------------------------------------------

char areg[maxdigits + 1];
char breg[maxdigits + 1];
char creg[maxdigits + 1];
char dreg[maxdigits + 1];
char ereg[maxdigits + 1];

//-------------------------------------------------------------------------------------------------------

char* makechararray(int nchars)
{
return (char *) malloc(nchars);
}

//-------------------------------------------------------------------------------------------------------

int chararraylength(char* chararray)
{
return strlen(chararray) + 1;
}

//-------------------------------------------------------------------------------------------------------

void copymemory(char* from, char* to)
{
int copylength = chararraylength(from);
memcpy(to, from, copylength);
}

//-------------------------------------------------------------------------------------------------------

void changechararray(char* change, char* tothis)
{
int newsize = chararraylength(tothis);
realloc(change, newsize);
copymemory(tothis, change);
}

//-------------------------------------------------------------------------------------------------------

char intval(char c)
{
return c - 48;
}
//-------------------------------------------------------------------------------------------------------

char charval(char c)
{
return c + 48;
}

//-------------------------------------------------------------------------------------------------------

void zeroreg(char* reg)
{
reg[0] = charval(0);
reg[1] = 0;
}

//-------------------------------------------------------------------------------------------------------

bool iszeroreg(char* reg)
{
if((reg[0]==charval(0)) && (reg[1]==0)) return true;
else return false;
}

//-------------------------------------------------------------------------------------------------------

void reversereg(char* reg)
{
int i;
int copylength = chararraylength(reg) - 1;
for(i=0; i<=copylength - 1; i++) ereg[copylength - 1 - i] = reg[i];
ereg[copylength] = 0;
changechararray(reg, ereg);
}

//-------------------------------------------------------------------------------------------------------

void shiftregright(char* reg, int nplaces)
{
int i;
if (iszeroreg(reg)) return;
int length = chararraylength(reg);
for(i=length; i>=0; i--) reg[i + nplaces] = reg[i];
for(i=nplaces; i>=0; i--) reg[i-1] = charval(0);
}

//-------------------------------------------------------------------------------------------------------

void multregbydigit(char* multreg, char* productreg, char cdigit)
{
int i;
char value, product, digit;
char multiplier = intval(cdigit);
char carry = 0;
int length = chararraylength(multreg) - 1;
if (multiplier==0)
{
zeroreg(productreg);
return;
}
for(i=0; i<length; i++)
{
value = intval(multreg[i]);
product = multiplier * value + carry;
digit = product % 10;
carry = product / 10;
productreg[i] = charval(digit);
}
if (carry > 0)
{
productreg[length] = charval(carry);
productreg[length + 1] = 0;
}
else productreg[length] = 0;
}

//-------------------------------------------------------------------------------------------------------

void addregs(char* reg1, char* reg2, char* sumreg)
{
int i, totallength;
char value1, value2, totalvalue, digit;
char carry = 0;
int length1 = chararraylength(reg1) - 1;
int length2 = chararraylength(reg2) - 1;
if (length1 >= length2) totallength = length1;
else totallength = length2;
for(i=0; i<totallength; i++)
{
if (i < length1) value1 = intval(reg1[i]);
else value1 = 0;
if (i < length2) value2 = intval(reg2[i]);
else value2 = 0;
totalvalue = value1 + value2 + carry;
digit = totalvalue % 10;
carry = totalvalue / 10;
sumreg[i] = charval(digit);
}
if (carry > 0)
{
sumreg[totallength] = charval(carry);
sumreg[totallength + 1] = 0;
}
else sumreg[totallength] = 0;
}

//-------------------------------------------------------------------------------------------------------

void multiplynums(char* num1, char* num2, char* productnum)
{
int areglength, i;
zeroreg(creg);
zeroreg(dreg);
reversecopynumtoreg(num1, areg);
reversecopynumtoreg(num2, breg);
areglength = chararraylength(areg) - 1;
for(i=0;i<areglength;i++)
{
multregbydigit(breg, creg, areg[i]);
shiftregright(creg, i);
addregs(creg, dreg, dreg);
}
reversereg(dreg);
changechararray(productnum, dreg);
}

//-------------------------------------------------------------------------------------------------------

void reversecopynumtoreg(char* num, char* reg)
{
copymemory(num, reg);
reversereg(reg);
}

//-------------------------------------------------------------------------------------------------------

void reversecopyregtonum(char* reg, char* num)
{
reversereg(reg);
copymemory(reg, num);
}

//-------------------------------------------------------------------------------------------------------

int main()
{
int maxchars = 10000;
char* numbuffer;
char* num1;
char* num2;
char* num3;
int numbufferlength;
clock_t ticks;
double seconds;

numbuffer = makechararray(maxchars);

numbuffer = "102161416980634352819009968456572716459394052861896193522693384659451316919065674521230360388207142076476337134008028816319725875402645363898565351989651617407171463803160423676505619229422019038787884551600508919245930292356633346078309397741421925519543964702467550604783761184883932290055648850389569762652716765738213650304303203727076205963002261965796623767960277600017607103179893762285081228280130489991049843728779809136845152970893425281769263292409153719726289210453637233512680131101192399565009108671109719414545709112842255484705441800975828762444086957808568395612416771914295429980437558339043986763741209849192067965663220186512727406722776651729507854993146108325672674849396042483286237436058446800249697578839660087301248843225828136109788446531245303438216933416608771636026218333609128899817557296948688215288631704790741320082993628007709232054357089857799089030700761618192168196284856276982687410324540521000487099959858038474104158705683418761044329014456436588741955311108096";

numbufferlength = chararraylength(numbuffer);
num1 = makechararray(numbufferlength);
copymemory(numbuffer, num1);

numbuffer = "292659060088046995732826159070292327565345725031060738459685802328067542413756344869737869966979962621788718546897635921436248328494364390757251270846629975294565841993453922896731191305149350001124760321348520589689983025732378046919302764500125098303581795945237162299962124453908217326796127584822500033428474242606618272218562028069891574154203293526476865678186916450349114806056983103586599319927860068748448731956212713713878342113139081329794650509750925605306286607159260281583827484536441732225294727289305985962713456078391181109600905253358644201650032263578987796061622360345954038271671145207320853867618561846638909084303935731968294464845340838288390072271427360574178120154542675047889055437331534971208999626303755671754066249006857782676320859206995965301600262308284026162203658686033076504189053953527436288441651333495840587930652104556325683072118039799849002859233592936653518659243669471363981369907418767362748010120808935308886571246929908292898706400495147917220830010157257";

numbufferlength = chararraylength(numbuffer);
num2 = makechararray(numbufferlength);
copymemory(numbuffer, num2);

num3 = makechararray(1);

multiplynums(num1, num2, num3);
printf("num1:\n");
printf("%s\n\n", num1);
printf("num2:\n");
printf("%s\n\n", num2);
printf("num3:\n");
printf("%s\n\n", num3);

ticks = clock();
seconds = (double)ticks / CLOCKS_PER_SEC;

printf("CPU time = %0.3f seconds\n\n", seconds);

return 0;
}

' output ------------------------------------------------------------------------------------------------

num1:
10216141698063435281900996845657271645939405286189619352269338465945131691906567
45212303603882071420764763371340080288163197258754026453638985653519896516174071
71463803160423676505619229422019038787884551600508919245930292356633346078309397
74142192551954396470246755060478376118488393229005564885038956976265271676573821
36503043032037270762059630022619657966237679602776000176071031798937622850812282
80130489991049843728779809136845152970893425281769263292409153719726289210453637
23351268013110119239956500910867110971941454570911284225548470544180097582876244
40869578085683956124167719142954299804375583390439867637412098491920679656632201
86512727406722776651729507854993146108325672674849396042483286237436058446800249
69757883966008730124884322582813610978844653124530343821693341660877163602621833
36091288998175572969486882152886317047907413200829936280077092320543570898577990
89030700761618192168196284856276982687410324540521000487099959858038474104158705
683418761044329014456436588741955311108096

num2:
29265906008804699573282615907029232756534572503106073845968580232806754241375634
48697378699669799626217887185468976359214362483284943643907572512708466299752945
65841993453922896731191305149350001124760321348520589689983025732378046919302764
50012509830358179594523716229996212445390821732679612758482250003342847424260661
82722185620280698915741542032935264768656781869164503491148060569831035865993199
27860068748448731956212713713878342113139081329794650509750925605306286607159260
28158382748453644173222529472728930598596271345607839118110960090525335864420165
00322635789877960616223603459540382716711452073208538676185618466389090843039357
31968294464845340838288390072271427360574178120154542675047889055437331534971208
99962630375567175406624900685778267632085920699596530160026230828402616220365868
60330765041890539535274362884416513334958405879306521045563256830721180397998490
02859233592936653518659243669471363981369907418767362748010120808935308886571246
929908292898706400495147917220830010157257

num3:
29898464270815493744673194269710642565047327679035346523308934412867642686794108
47947199420370032347855374731546145313227658615559597160070582230505916920657829
04599579419915761635142044593055321382677642443198817969891643755040346161981066
46932812614240771247719983060093133564506822520127786153042706475830934585272978
07233061674340151380560169031567087980109266570976195024720572250904502237858082
93363343155653427592007963536127596119876438198871979069825862432128614114942447
08585041393104153364632370804692624166484492347572124998885796837421851159817331
85729954738924979566043667371707165115972908643512267078865992355195128473479020
70600419416678885147597895371318742244180119600470219209129010407502785940261100
58228190763394615276915650969412751686582607197564903207373559828942368525300782
79093559875306473730471308853287864908961130049418777790958492274628497884044827
21592123484376759612740353644493698230341467771441692299605423610592549100556278
19461128367235273694749534751061781239008188669961796434628458363505027957236815
60224733749668563931802817830064817196298641435558596324453555349681448559675221
02829216746826829145063931048236824770878307460607738186825789823439143879831909
64254893643317572188276629548252122933353567771594235819918749252239809497459088
00494408626750270317949805306412526960128603629218339164932593621321242313164098
50390761303304543746601100295707181573060234715295710493481352966314416956394259
05378354034189779116735299398900444542980113384949085017981339044611412523801339
55241799478043675865168280207629607657646285483670823980433031722505427726223822
91071864398221884932527779242259881099192047788536430654924612246363812604252816
10999950814577675804883080550315414363420196347774483980831166945295021486843989
81476738892845139727267950182279525060990400275228966234813836941071516979510364
50487326472186274696189845738530352994630454253049758378526425722302342472640098
86637014491869855156528302649694850583069000308286874099288423643379617119885852
672

CPU time = 0.192 seconds

Press any key to continue...

[zak]

my cpu time 0.437 seconds, my cpu pentium D 3GH, 3GB Ram
so your cpu are speedier , my cpu is one of the oldest dual core cpu's ,thanks for this program, usefull for c learning.

[danbaron]

I am relieved that it ran OK for you, zak.

The worst case is when it runs for one person, but it doesn't run for another.

[danbaron]

I modified the program a little.

I changed the code so that the elapsed time would only be for multiplying the two integers.

Then, I compiled and ran it using GCC instead of Pelles C.

I had to add the line,



gets(areg);
at the end of the program. Otherwise the console just flashes on the screen and disappears.

I compiled it by changing the directory to the folder containing the source code (main.c), and then executing the command,



> gcc -O3 main.c -o mult.exe
"-O3" means, the greatest possible optimization.

Then, I ran it by executing the command,



> mult
I ran it thrice, and the times were,

0.038 seconds
0.034 seconds
0.033 seconds


' modified code -------------------------------------------------------

int main()
{
.
.
clock_t ticks1, ticks2, totalticks;
.
.
ticks1 = clock();
multiplynums(num1, num2, num3);
ticks2 = clock();
totalticks = ticks2 - ticks1;
seconds = (double)totalticks / CLOCKS_PER_SEC;
.
.
gets(areg);
return(0);
}

[danbaron]

I have the 3rd edition of Volume 2 of, "The Art of Computer Programming", by Donald Knuth - Semi-Numerical Algorithms.

In it, he shows different ways to do fast multiplication on big integers.

He is the smartest numerical computer scientist I know of, and most of his methods are really complicated.

Here I compare the pencil and paper method, to the simplest method he shows, which is slightly faster.

He doesn't even name this method, so I will call it the splitting method.

I can show the splitting method by an example.

Say we want to multiply 1234 times 5678.

We all know how to do it with a pencil and paper.

For the splitting method we write,

1234 = 10^2 * 12 + 34,

5678 = 10^2 * 56 + 78.

So,

1234 * 5678 =

(10^2 * 12 + 34) * (10^2 * 56 + 78 ).

= 10^4 * 12 * 56 + 10^2 * 12 * 78 + 10^2 * 56 * 34 + 34 * 78.

It turns out that the multiplications by the factors 10^4 and 10^2 are, for the computer, just register shifts.

So, instead of doing one big multiplication, we do four smaller ones (each of the smaller multiplications is still done by the computer using the pencil and paper method).

If you look at the code, in function main(), you'll see that the splitting method requires more register copying, shifting and additions, but, it's still faster than instead doing just one big multiplication.

As I've shown the method, and as it appears below in the code, each number is split into two parts, and therefore, there are four multiplications. But, you can extend the method and, for instance, split each number into three parts, giving nine multiplications, etc.

But anyway, there are much faster ways to multiply large integers than this one.

In the program, the numbers num1 and num2 are multiplied twice, once by each method.

num1 = 1565^1565 (5000 digits)

num2 = 1564^1566 (5003 digits)

num3 = num1 * num2 (10002 digits)

pencil and paper method
4.918 seconds

splitting method
4.009 seconds

So, the splitting method takes approximately 18% less time than the pencil and paper method (on my computer using Pelles C).

(
Comment:
To me, the hardest part about using C, is that when you do something wrong, there are no error messages, the program just crashes. And it is left for you to try to track down what caused the crash.
)

(
Comment:
I timed the multiplication using Racket, in the DrRacket IDE. The time was 0.001 seconds!
)

:o


' code ---------------------------------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <time.h>

#define maxdigits 50000

//-------------------------------------------------------------------------------------------------------

char* makechararray(int nchars);
int chararraylength(char* chararray);
void copymemory(char* from, char* to);
void copymemory2(char* from, char* to, int length);
void changechararray(char* change, char* tothis);
char intval(char c);
char charval(char c);
void zeroreg(char* reg);
bool iszeroreg(char* reg);
void reversereg(char* reg);
void shiftregright(char* reg, int nplaces);
void multregbydigit(char* multreg, char* productreg, char cdigit);
void addregs(char* reg1, char* reg2, char* sumreg);
void multiplynums(char* n1, char* n2, char* productnum);
void reversecopynumtoreg(char* num, char* reg);
void reversecopyregtonum(char* reg, char* num);

//-------------------------------------------------------------------------------------------------------

char areg[maxdigits + 1];
char breg[maxdigits + 1];
char creg[maxdigits + 1];
char dreg[maxdigits + 1];
char ereg[maxdigits + 1];
char freg[maxdigits + 1];
char greg[maxdigits + 1];

//-------------------------------------------------------------------------------------------------------

char* makechararray(int nchars)
{
return (char *) malloc(nchars);
}

//-------------------------------------------------------------------------------------------------------

int chararraylength(char* chararray)
{
return strlen(chararray) + 1;
}

//-------------------------------------------------------------------------------------------------------

void copymemory(char* from, char* to)
{
int copylength = chararraylength(from);
memcpy(to, from, copylength);
}
//-------------------------------------------------------------------------------------------------------

void copymemory2(char* from, char* to, int length)
{
memcpy(to, from, length);
}

//-------------------------------------------------------------------------------------------------------

void changechararray(char* change, char* tothis)
{
int newsize = chararraylength(tothis);
realloc(change, newsize);
copymemory(tothis, change);
}

//-------------------------------------------------------------------------------------------------------

char intval(char c)
{
return c - 48;
}
//-------------------------------------------------------------------------------------------------------

char charval(char c)
{
return c + 48;
}

//-------------------------------------------------------------------------------------------------------

void zeroreg(char* reg)
{
reg[0] = charval(0);
reg[1] = 0;
}

//-------------------------------------------------------------------------------------------------------

bool iszeroreg(char* reg)
{
if((reg[0]==charval(0)) && (reg[1]==0)) return true;
else return false;
}

//-------------------------------------------------------------------------------------------------------

// This procedure was wrong in the previous source code.

void reversereg(char* reg)
{
int i;
int copylength = chararraylength(reg) - 1;
for(i=0; i<=copylength - 1; i++) ereg[copylength - 1 - i] = reg[i];
ereg[copylength] = 0;
for(i=0; i<=copylength; i++) reg[i] = ereg[i];
}

//-------------------------------------------------------------------------------------------------------

void shiftregright(char* reg, int nplaces)
{
int i;
if (iszeroreg(reg)) return;
int length = chararraylength(reg);
for(i=length; i>=0; i--) reg[i + nplaces] = reg[i];
for(i=nplaces; i>=0; i--) reg[i-1] = charval(0);
}

//-------------------------------------------------------------------------------------------------------

void multregbydigit(char* multreg, char* productreg, char cdigit)
{
int i;
char value, product, digit;
char multiplier = intval(cdigit);
char carry = 0;
int length = chararraylength(multreg) - 1;
if (multiplier==0)
{
zeroreg(productreg);
return;
}
for(i=0; i<length; i++)
{
value = intval(multreg[i]);
product = multiplier * value + carry;
digit = product % 10;
carry = product / 10;
productreg[i] = charval(digit);
}
if (carry > 0)
{
productreg[length] = charval(carry);
productreg[length + 1] = 0;
}
else productreg[length] = 0;
}

//-------------------------------------------------------------------------------------------------------

void addregs(char* reg1, char* reg2, char* sumreg)
{
int i, totallength;
char value1, value2, totalvalue, digit;
char carry = 0;
int length1 = chararraylength(reg1) - 1;
int length2 = chararraylength(reg2) - 1;
if (length1 >= length2) totallength = length1;
else totallength = length2;
for(i=0; i<totallength; i++)
{
if (i < length1) value1 = intval(reg1[i]);
else value1 = 0;
if (i < length2) value2 = intval(reg2[i]);
else value2 = 0;
totalvalue = value1 + value2 + carry;
digit = totalvalue % 10;
carry = totalvalue / 10;
sumreg[i] = charval(digit);
}
if (carry > 0)
{
sumreg[totallength] = charval(carry);
sumreg[totallength + 1] = 0;
}
else sumreg[totallength] = 0;
}

//-------------------------------------------------------------------------------------------------------

void multiplynums(char* num1, char* num2, char* productnum)
{
int areglength, i;
zeroreg(creg);
zeroreg(dreg);
reversecopynumtoreg(num1, areg);
reversecopynumtoreg(num2, breg);
areglength = chararraylength(areg) - 1;
for(i=0;i<areglength;i++)
{
multregbydigit(breg, creg, areg[i]);
shiftregright(creg, i);
addregs(creg, dreg, dreg);
}
reversereg(dreg);
changechararray(productnum, dreg);
}

//-------------------------------------------------------------------------------------------------------

void reversecopynumtoreg(char* num, char* reg)
{
copymemory(num, reg);
reversereg(reg);
}

//-------------------------------------------------------------------------------------------------------

void reversecopyregtonum(char* reg, char* num)
{
reversereg(reg);
copymemory(reg, num);
}

//-------------------------------------------------------------------------------------------------------

int main()
{
int maxchars = 20000;
char* numbuffer;
char* num1;
char* num2;
char* num3;
char* num4;
char* num5;
char* num6;
char* num7;
int numbufferlength;
int leftbufferlength1;
int rightbufferlength1;
int leftbufferlength2;
int rightbufferlength2;
clock_t ticks1, ticks2, totalticks;
double seconds;

numbuffer = makechararray(maxchars);

// num1 = 1565^1565

numbuffer = "\
25998305698778882782694282216427520062325059925056858892956364318072249183875081684424630961752645071829620406259524052715060610486050318728348276382757621322537385844563410552297\
03960182489849843615430088190470906264709925195692664930112398138571316164112551306702883093681147292350025702486270799158479897114054161730071234231202135809223242312655616315542\
94858343807188790751402459010233773238407873247871862406989702271177063193217340225057994600159267813767262212104205783683630250951779202250748346696462525454084274493510695150600\
97278605753619956900553867954076817448024435352255848859957690927310303677723596457787879480350715750825350328986324045895598243176085969044169791618738993283910620831103810475946\
33049203806694209608683892867150595141099756215041900582804111939062007092622474933044811876158602334452145258026429850607093412457930099562830313117366885751915651353104749583302\
15531787533896617511151902175564933090237349475682507288214834576209815927063905016273599569214838817459219798765924129592642265326108449655330560382382808271594777451322142493737\
50436634764123083968071055694200079842493400807012422680542410393489626517468028967370112652092983565987174897956418497929373045550019576989200303483284173094578415208174108966111\
65769767114391007120100420915169233837546621367856373302160998891694535450327805786016482732217698026063614406032639393593323756983641365852805399102913705624570668116080267832367\
64726683132531914526690079457415699556325344231253602665256734457103448932253363180362275189980249038592241415696321784878512266463323578847913879046543862149605315487173265449103\
44985254212880143267315626819963685160364936678345613170342983101939558616468939108822708875327843669816436591423630016096816579847927321181094384808489711445890318046103329755131\
62952739089719888839081179410446068318437603084717680650172030192284372699875462519689409497103701529019146230799704955103121558571053162856032846963053023073895580770204846561803\
19793653498159544887791694640438098310707665084132391468679417809075146524582340076967046467032663807608084498486090543541686857510467272349459625744971256146278089920197008015202\
02690113820825817340003057701196678502919432716213170216770030043873909619982612504305878265633841170539161255126910093406488152402014905107844865504985975694570452768848049186511\
99343974854638155380738541969317159047708071490994665030286091840214412215908967522889330586157041819473261044582655233984838954869758582863093426501294751819363488772591396849482\
14541231696731536480114115069165287234606436467155715957870568873819933917795169659740301812765066254701635819988078720330945566076017124663839115674714319451320282844920088886274\
73183080652614885161771855164380212565129787480664319435252412243109730118888371736549215790484028504236717022689894947667447117982384625105846406370847334996010683331030678681427\
56427363881319487885330401465342823767881986629761083854935148599074348338648707137178894243135645129870888909362061936491534282424966231253781963484583313517427756831015160329084\
60421876455141368075149317323870087337557877266063706878152841099564845544576025849122752684922700102768063842022852201618436041096969316122507106954031660961201152487601068885764\
19087725518021013593600262995448253448543521153012842991260187150278738361140333399022055405953281564677515388599440587422064155578156817459134199947346374100959559692603359039655\
24334122036308511201866709174269603063778755681701026350607067305932389961340795092328701602727982045965114355375309786443302187387677733514059550562299023733263296576813373658598\
84155874806028591436772424316939960794574765085028914727655378379459371910837700308282017621308703102279516109620292854140593361925457498990624664484126521180443327638609256610715\
82419939836634496774665279093978101639317890062004035158543041690432702567221611683434360955191759751176141733345322786732343897113347147010081549975643292804851441713936816718754\
75203079259426309412509694297381930371443878319798964013436284657801174397785118092847511855767525967405542569731376220819573179017358826348414526450228259798198209358429448216351\
87295580951120792676121655839110764857384570681249408390387336607185144639704928963678599968065764930847785365152347532233552576705584073135488835033287183224933798541691954594398\
98333887079542214646235864356921050476220943937551133229566137714685998165093616730709543866077509213332725389374230923815844390925073374824071362988069361361011255967699497866661\
62714841452877314930577231653669903532722035593269784295966890513044297239172109719876364689715311254024899745850588930498595823251631264631173564483117330017864990279267177572324\
35656629842359245452820345956459909201496694299826694363861604887856263567748856093177664375222549588154447598478535276027080215208489307640259709395796603894282589230696206726925\
56578816868263589345214720402757856535244008389116357181992863100461445950794646004645924711561995664374903749492728661653448592183668353072789614088833332061767578125";

numbufferlength = chararraylength(numbuffer); num1 = makechararray(numbufferlength); copymemory(numbuffer, num1);

// Divide the string for num1 into halves.

leftbufferlength1 = (numbufferlength - 1) / 2;
rightbufferlength1 = numbufferlength - 1 - leftbufferlength1;

// num4 is the left half of num1.
num4 = makechararray(leftbufferlength1 + 1);

// num5 is the right half of num1.
num5 = makechararray(rightbufferlength1 + 1);

copymemory2(numbuffer, num4, leftbufferlength1);
strcat(num4, "\0");
copymemory2(numbuffer + leftbufferlength1, num5, rightbufferlength1);
strcat(num5, "\0");

// num2 = 1564^1566

numbuffer = "\
14953694418600598137797892976168196776550567060529797819121509629371302803543047947100026386030253936809331859893109397981441734931992474450663129199455045572910284842176406899012\
43307622714965754048859748977920315548552684814674994364164951139260855448178060157456685670415726352514465858604473206508032550589348599881678743369109149811460642052784089771422\
91744415137914234657570985630122391641558757994793525336676787152374526553521316997756026971178406162991176203118480489761094622115846192860175725211188264259166267492428995258110\
83683907649791133130877994971132411816207015370755703514028461716861110300326545169051323939067656566373301272620855075647555506321187475534683658318074908480834384731815036732634\
82858395516104456338345864555593262669916685657966382646844046866252988586196209737157516637209718863572931976654319891599277473185165878816845974781435780684185989999957487383831\
37861925308297636682237514758155596269988917999368638114799054174138930419001043614365097024322487136127353937477973446705732154671588371246649431940951731178168927368725123487729\
03771697996577386307417031230349886957523265128233630357733358656165643541869349027855435790150989362395180774169792155845865791329928242819582039416749235148627494709871544555020\
10093324654473516620475885269703536176341896090069366921600832763359675089171251343765236529648019050977560844310113870723363074154261375145861092865638405899047624663287724736360\
80476570473845749834946205966830068246068081055301618114115160260567957400406556226799051150155476897434294515025174020402128851623296484796653860254811329408845863084135782921536\
21483726866822491840720165305477713243852611546603949257573919201693347019306877933275222402190674678219165949517721242004971360669326466380830023692972980861068704768448043607886\
71423944136093456527786040949331054778122595410580450575629487259866067631083443206975004661365278327745764540671388719699149525390448071738778331668776093407133995815843944327218\
44665956342684071503071107022242837863889795149361395266882979889753442262605933142862525196227636432619247162948483815669265297033419502214095114217328465436045481752075057310608\
44137720865695818022430570333219854583320117700195969473115380643833520674709196440916318387310069492829393841228234955558630366974716594286601533756947679648847579611676791212434\
40028060803325441354945609819663260483975637672527300005951101097016242870505527019762222302185565802468710433554443789441694256848840008154289267824103969873333154288205338600609\
77842752054812402996259937871008789825718924504985019890927788235251272998474212768045082439287089460080388852001455593433597194810757462132468056513501635633081007257649483112682\
34822501637453283225820881849606453267653519474313200805526606359083453509438000385003910951061856642587227716696892881885276438012629059859421937780214247605390680174843587561946\
18314656471218118039863663105461283739860742984199751430980056375347609884716204802408420601758404838089035474738962736283217374264765883445306310888553952447712151286626105775549\
73952543853157493575398455081916020756387754825722911462995957383017698708383569724166635814416023587521247552730824708256637879634438550373052235144370852480099093802037072882646\
32614358321432421646474758581779379273787711138284057636642225697503641601929401639008102855704825605385587400170088108865486989656844307256957096459406069983892667934860590594212\
64207090035352881784015144399076714770706583186958602234705999155280559159818075169130946134849669862352857408492655215371517430222717010480652982755587164565554865565137968942281\
30585907963279591693153127385537915504305139241778224122264166888707590254339186101506086374607915696247286880300273718183576480051736136229327209786466661828280717095099432518258\
62112857275386877828198053625783207675184392555330989527083393662182134933588727503843287271421499880958129106541726815265795925097182446884331285888015088738822106103494604839411\
71935273403293012896725297262632231479350344860770189200228711727280744694520246536474683168581083789150032910734207493731481478817765652323081725837341371502685169550084905042551\
94968300754792052664802355492330949582901902540110000531949620448375823368348626374459486370104038386643463775570215027986887983173680297564514867086636686849893527912763767483845\
54870037178075416211081932500451458152686939788972837260816169766577003587059851122359323070088850008363994264651072287273196241809330233010117528732688007449247574878428548398386\
73206500345267401423739778376321951113447393076114319524366256754477382584302212545897813368138475067522929127800802677805576775240634181480490016951352798893453287748010286982821\
32388239449368378252259247675901904409790567434116208634661532264437633169790035015446526660783709640299285895702764613315509042135055117925041047687444744230328743205855947338429\
96027579206308099156305659536475366018471863849833694124608532854592685582553705477203558891515273967068330509324599307015184379886050781984586886687451347845490289934336";

numbufferlength = chararraylength(numbuffer);
num2 = makechararray(numbufferlength); copymemory(numbuffer, num2);

// Divide the string for num2 into halves.

leftbufferlength2 = (numbufferlength - 1) / 2;
rightbufferlength2 = numbufferlength - 1 - leftbufferlength2;

// num6 is the left half of num2.
num6 = makechararray(leftbufferlength2 + 1);

// num7 is the right half of num2.
num7 = makechararray(rightbufferlength2 + 1);

copymemory2(numbuffer, num6, leftbufferlength2);
strcat(num6, "\0");
copymemory2(numbuffer + leftbufferlength2, num7, rightbufferlength2);
strcat(num7, "\0");

num3 = makechararray(1);

// First multiply the regular way.
// num3 = num1 * num2

ticks1 = clock();
multiplynums(num1, num2, num3);
ticks2 = clock();

totalticks = ticks2 - ticks1;

seconds = (double)totalticks / CLOCKS_PER_SEC;
printf("num3:\n");
printf("%s\n\n", num3);
printf("CPU time = %0.3f seconds\n\n", seconds);

// Now multiply the faster way.

// num1 = 10^a * num4 + num5 (where a equals the number of digits in num5)

// num2 = 10^b * num6 + num7 (where b equals the number of digits in num7)

// num3 = num1 * num2
// num3 = (10^a * num4 + num5) * (10^b * num6 + num7)
// num3 = 10^(a + b) * num4 * num6 + 10^a * num4 * num7 + 10^b * num5 * num6 + num5 * num7

ticks1 = clock();

multiplynums(num4, num6, num3);
reversecopynumtoreg(num3, freg);
shiftregright(freg, rightbufferlength1 + rightbufferlength2);

multiplynums(num4, num7, num3);
reversecopynumtoreg(num3, greg);
shiftregright(greg, rightbufferlength1);
addregs(freg, greg, freg);

multiplynums(num5, num6, num3);
reversecopynumtoreg(num3, greg);
shiftregright(greg, rightbufferlength2);
addregs(freg, greg, freg);

multiplynums(num5, num7, num3);
reversecopynumtoreg(num3, greg);
addregs(freg, greg, freg);

reversecopyregtonum(freg, num3);

ticks2 = clock();

totalticks = ticks2 - ticks1;

seconds = (double)totalticks / CLOCKS_PER_SEC;
printf("num3:\n");
printf("%s\n\n", num3);
printf("CPU time = %0.3f seconds\n\n", seconds);

return 0;
}

' output -------------------------------------------------------------------------------------------

num3:
38877071882090190287243874066386570996106180815191290171670322173603050890718429
74839028108882950240647661332671208576010397320739581794493589311660281327350234
06492218502077670022374391395599997717369353378622092485707481885985734972182603
85437954061111244953699266944224514417026783219651579942657699019820344297363624
29939747376167795300959349781206808406606619163241179315199315603041371231647287
.
. (I can't show the entire 10002 digits. The post would exceed the size limit.)
.
66312829630749831470345642557743672204753069124860314880002595514719331976847645
34136311903926521773288199634781312147637457108185599929362483272943295821515226
67822418597140080136863790150389885957293790959823788393311970524106891986604950
05843114107098780270671447317251982737665033091542966229614782505107176119888699
01502707423870264316849802231561584640000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00

CPU time = 4.918 seconds

num3:
38877071882090190287243874066386570996106180815191290171670322173603050890718429
74839028108882950240647661332671208576010397320739581794493589311660281327350234
06492218502077670022374391395599997717369353378622092485707481885985734972182603
85437954061111244953699266944224514417026783219651579942657699019820344297363624
29939747376167795300959349781206808406606619163241179315199315603041371231647287
.
. (I can't show the entire 10002 digits. The post would exceed the size limit.)
.
66312829630749831470345642557743672204753069124860314880002595514719331976847645
34136311903926521773288199634781312147637457108185599929362483272943295821515226
67822418597140080136863790150389885957293790959823788393311970524106891986604950
05843114107098780270671447317251982737665033091542966229614782505107176119888699
01502707423870264316849802231561584640000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00

CPU time = 4.009 seconds

Press any key to continue...

[jack]

Dan, the LibTomMath that I mentioned earlier also includes a book named "bn.pdf" for big number and also "tommath.pdf"
it discusses the different algorithms used.
I ran a test in ThinBasic with your numbers and in a 10000 loop it timed at 3.7 seconds or 0.00037 seconds per multiply.



Type mp_int
used as long
alloc as long
sign As Long
dp As Long Ptr
End Type
%DIGIT_BIT = 28
%MP_DIGIT_BIT = 28
%MP_LT = -1
%MP_EQ = 0
%MP_GT = 1
%MP_ZPOS = 0
%MP_NEG = 1
%MP_OKAY = 0
%MP_MEM = -2
%MP_VAL = -3
%MP_RANGE = -3
%MP_YES = 1
%MP_NO = 0
%LTM_PRIME_BBS = &h0001
%LTM_PRIME_SAFE = &h0002
%LTM_PRIME_2MSB_ON = &h0008
%MP_PREC = 32
%PRIME_SIZE = 256 'Number of primes In ltm_prime_tab()
'*** the following are constants in the library but don't know how to import them
' KARATSUBA_MUL_CUTOFF As Long
' KARATSUBA_SQR_CUTOFF as long
' TOOM_MUL_CUTOFF as long
' TOOM_SQR_CUTOFF as long
' ltm_prime_tab As Long 'the first 256 primes
' mp_s_rmap as string
Declare Sub mp_error_to_string CDECL Lib "libtom.dll" Alias "mp_error_to_string" (ByRef code As Long) 'char*
Declare Function mp_init CDECL Lib "libtom.dll" Alias "mp_init" (ByRef a As mp_int) As Long
Declare Sub mp_clear CDECL Lib "libtom.dll" Alias "mp_clear" (ByRef a As mp_int)

'*** these function/sub use variable number of arguments with a 0 for the last argument to indicate the end
Declare Function mp_init_multi CDECL Lib "libtom.dll" Alias "mp_init_multi" _
(ByRef mp1 As mp_int, Optional ByRef mp2 As mp_int, ByRef mp3 As mp_int, ByRef mp4 As mp_int, _
ByRef mp5 As mp_int, ByRef mp6 As mp_int, ByRef mp7 As mp_int, ByVal null_ As Long) As Long
Declare Sub mp_clear_multi CDECL Lib "libtom.dll" Alias "mp_clear_multi" _
(ByRef mp1 As mp_int, Optional ByRef mp2 As mp_int, ByRef mp3 As mp_int, ByRef mp4 As mp_int, _
ByRef mp5 As mp_int, ByRef mp6 As mp_int, ByRef mp7 As mp_int, ByVal null_ As Long) As Long
Declare Sub mp_exch CDECL Lib "libtom.dll" Alias "mp_exch" (ByRef a As mp_int, ByRef b As mp_int)
Declare Function mp_shrink CDECL Lib "libtom.dll" Alias "mp_shrink" (ByRef a As mp_int)
Declare Function mp_grow CDECL Lib "libtom.dll" Alias "mp_grow" (ByRef a As mp_int, ByVal Sizen As Long) As Long
Declare Function mp_init_size CDECL Lib "libtom.dll" Alias "mp_init_size" (ByRef a As mp_int, ByVal Sizen As Long) As Long
Declare Sub mp_zero CDECL Lib "libtom.dll" Alias "mp_zero" (ByRef a As mp_int)
Declare Sub mp_set CDECL Lib "libtom.dll" Alias "mp_set" (ByRef a As mp_int, ByVal b As Long)
Declare Function mp_set_int CDECL Lib "libtom.dll" Alias "mp_set_int" (ByRef a As mp_int, ByVal b As Long) As Long
Declare Function mp_get_int CDECL Lib "libtom.dll" Alias "mp_get_int" (ByRef a As mp_int) As Long
Declare Function mp_init_set CDECL Lib "libtom.dll" Alias "mp_init_set" (ByRef a As mp_int, ByVal b As Long) As Long
Declare Function mp_init_set_int CDECL Lib "libtom.dll" Alias "mp_init_set_int" (ByRef a As mp_int, ByVal b As Long) As Long
Declare Function mp_copy CDECL Lib "libtom.dll" Alias "mp_copy " (ByRef a As mp_int, ByRef b As mp_int) As Long
Declare Function mp_init_copy CDECL Lib "libtom.dll" Alias "mp_init_copy" (ByRef a As mp_int, ByRef b As mp_int) As Long
Declare Sub mp_clamp CDECL Lib "libtom.dll" Alias "mp_clamp" (ByRef a As mp_int)
Declare Sub mp_rshd CDECL Lib "libtom.dll" Alias "mp_rshd" (ByRef a As mp_int, ByVal b As Long)
Declare Function mp_lshd CDECL Lib "libtom.dll" Alias "mp_lshd" (ByRef a As mp_int, ByVal b As Long) As Long
Declare Function mp_div_2d CDECL Lib "libtom.dll" Alias "mp_div_2d" (ByRef a As mp_int, b As Long, ByRef c As mp_int, ByRef d As mp_int) As Long
Declare Function mp_div_2 CDECL Lib "libtom.dll" Alias "mp_div_2" (ByRef a As mp_int, ByRef b As mp_int) As Long
Declare Function mp_mul_2d CDECL Lib "libtom.dll" Alias "mp_mul_2d" (ByRef a As mp_int, b As Long, ByRef c As mp_int) As Long
Declare Function mp_mul_2 CDECL Lib "libtom.dll" Alias "mp_mul_2" (ByRef a As mp_int, ByRef b As mp_int) As Long
Declare Function mp_mod_2d CDECL Lib "libtom.dll" Alias "mp_mod_2d" (ByRef a As mp_int, b As Long, ByRef c As mp_int) As Long
Declare Function mp_2expt CDECL Lib "libtom.dll" Alias "mp_2expt" (ByRef a As mp_int, ByVal b As Long) As Long
Declare Function mp_cnt_lsb CDECL Lib "libtom.dll" Alias "mp_cnt_lsb" (ByRef a As mp_int) As Long
Declare Function mp_rand CDECL Lib "libtom.dll" Alias "mp_rand" (ByRef a As mp_int, ByVal digits As Long) As Long
Declare Function mp_xor CDECL Lib "libtom.dll" Alias "mp_xor" (ByRef a As mp_int, ByRef b As mp_int, ByRef c As mp_int) As Long
Declare Function mp_or CDECL Lib "libtom.dll" Alias "mp_or" (ByRef a As mp_int, ByRef b As mp_int, ByRef c As mp_int) As Long
Declare Function mp_and CDECL Lib "libtom.dll" Alias "mp_and" (ByRef a As mp_int, ByRef b As mp_int, ByRef c As mp_int) As Long
Declare Function mp_neg CDECL Lib "libtom.dll" Alias "mp_neg" (ByRef a As mp_int, ByRef b As mp_int) As Long
Declare Function mp_abs CDECL Lib "libtom.dll" Alias "mp_abs" (ByRef a As mp_int, ByRef b As mp_int) As Long
Declare Function mp_cmp CDECL Lib "libtom.dll" Alias "mp_cmp" (ByRef a As mp_int, ByRef b As mp_int) As Long
Declare Function mp_cmp_mag CDECL Lib "libtom.dll" Alias "mp_cmp_mag" (ByRef a As mp_int, ByRef b As mp_int) As Long
Declare Function mp_add CDECL Lib "libtom.dll" Alias "mp_add" (ByRef a As mp_int, ByRef b As mp_int, ByRef c As mp_int) As Long
Declare Function mp_sub CDECL Lib "libtom.dll" Alias "mp_sub" (ByRef a As mp_int, ByRef b As mp_int, ByRef c As mp_int) As Long
Declare Function mp_mul CDECL Lib "libtom.dll" Alias "mp_mul" (ByRef a As mp_int, ByRef b As mp_int, ByRef c As mp_int) As Long
Declare Function mp_sqr CDECL Lib "libtom.dll" Alias "mp_sqr" (ByRef a As mp_int, ByRef b As mp_int) As Long
Declare Function mp_div CDECL Lib "libtom.dll" Alias "mp_div" (ByRef a As mp_int, ByRef b As mp_int, ByRef c As mp_int, ByRef d As mp_int) As Long
Declare Function mp_mod CDECL Lib "libtom.dll" Alias "mp_mod" (ByRef a As mp_int, ByRef b As mp_int, ByRef c As mp_int) As Long
Declare Function mp_cmp_d CDECL Lib "libtom.dll" Alias "mp_cmp_d" (ByRef a As mp_int, ByVal b As Long) As Long
Declare Function mp_add_d CDECL Lib "libtom.dll" Alias "mp_add_d" (ByRef a As mp_int, ByVal b As Long, ByRef c As mp_int) As Long
Declare Function mp_sub_d CDECL Lib "libtom.dll" Alias "mp_sub_d" (ByRef a As mp_int, ByVal b As Long, ByRef c As mp_int) As Long
Declare Function mp_mul_d CDECL Lib "libtom.dll" Alias "mp_mul_d" (ByRef a As mp_int, ByVal b As Long, ByRef c As mp_int) As Long
Declare Function mp_div_d CDECL Lib "libtom.dll" Alias "mp_div_d" (ByRef a As mp_int, ByVal b As Long, ByRef c As mp_int, ByRef d As Long) As Long
Declare Function mp_div_3 CDECL Lib "libtom.dll" Alias "mp_div_3" (ByRef a As mp_int, ByRef c As mp_int, ByRef d As Long) As Long
Declare Function mp_expt_d CDECL Lib "libtom.dll" Alias "mp_expt_d" (ByRef a As mp_int, ByVal b As Long, ByRef c As mp_int) As Long
Declare Function mp_mod_d CDECL Lib "libtom.dll" Alias "mp_mod_d" (ByRef a As mp_int, ByVal b As Long, ByRef c As Long) As Long
Declare Function mp_addmod CDECL Lib "libtom.dll" Alias "mp_addmod" (ByRef a As mp_int, ByRef b As mp_int, ByRef c As mp_int, ByRef d As mp_int) As Long
Declare Function mp_submod CDECL Lib "libtom.dll" Alias "mp_submod" (ByRef a As mp_int, ByRef b As mp_int, ByRef c As mp_int, ByRef d As mp_int) As Long
Declare Function mp_mulmod CDECL Lib "libtom.dll" Alias "mp_mulmod" (ByRef a As mp_int, ByRef b As mp_int, ByRef c As mp_int, ByRef d As mp_int) As Long
Declare Function mp_sqrmod CDECL Lib "libtom.dll" Alias "mp_sqrmod" (ByRef a As mp_int, ByRef b As mp_int, ByRef c As mp_int) As Long
Declare Function mp_invmod CDECL Lib "libtom.dll" Alias "mp_invmod" (ByRef a As mp_int, ByRef b As mp_int, ByRef c As mp_int) As Long
Declare Function mp_gcd CDECL Lib "libtom.dll" Alias "mp_gcd" (ByRef a As mp_int, ByRef b As mp_int, ByRef c As mp_int) As Long
Declare Function mp_exteuclid CDECL Lib "libtom.dll" Alias "mp_exteuclid" (ByRef a As mp_int, ByRef b As mp_int, ByRef U1 As mp_int, ByRef U2 As mp_int, ByRef U3 As mp_int) As Long
Declare Function mp_lcm CDECL Lib "libtom.dll" Alias "mp_lcm" (ByRef a As mp_int, ByRef b As mp_int, ByRef c As mp_int) As Long
Declare Function mp_n_root CDECL Lib "libtom.dll" Alias "mp_n_root" (ByRef a As mp_int, b As Long, ByRef c As mp_int) As Long
Declare Function mp_sqrt CDECL Lib "libtom.dll" Alias "mp_sqrt" (ByRef arg As mp_int, ByRef ret As mp_int) As Long
Declare Function mp_is_square CDECL Lib "libtom.dll" Alias "mp_is_square" (ByRef arg As mp_int, ByRef ret As Long) As Long
Declare Function mp_jacobi CDECL Lib "libtom.dll" Alias "mp_jacobi" (ByRef a As mp_int, ByRef n As mp_int, ByRef c As Long) As Long
Declare Function mp_reduce_setup CDECL Lib "libtom.dll" Alias "mp_reduce_setup" (ByRef a As mp_int, ByRef b As mp_int) As Long
Declare Function mp_reduce CDECL Lib "libtom.dll" Alias "mp_reduce" (ByRef a As mp_int, ByRef b As mp_int, ByRef c As mp_int) As Long
Declare Function mp_montgomery_setup CDECL Lib "libtom.dll" Alias "mp_montgomery_setup" (ByRef a As mp_int, ByRef mp As Long) As Long
Declare Function mp_montgomery_calc_normalization CDECL Lib "libtom.dll" Alias "mp_montgomery_calc_normalization" (ByRef a As mp_int, ByRef b As mp_int) As Long
Declare Function mp_montgomery_reduce CDECL Lib "libtom.dll" Alias "mp_montgomery_reduce" (ByRef a As mp_int, ByRef m As mp_int, ByVal mp As Long) As Long
Declare Function mp_dr_is_modulus CDECL Lib "libtom.dll" Alias "mp_dr_is_modulus" (ByRef a As mp_int) As Long
Declare Sub mp_dr_setup CDECL Lib "libtom.dll" Alias "mp_dr_setup" (ByRef a As mp_int, ByRef d As Long)
Declare Function mp_dr_reduce CDECL Lib "libtom.dll" Alias "mp_dr_reduce" (ByRef a As mp_int, ByRef b As mp_int, ByVal mp As Long) As Long
Declare Function mp_reduce_is_2k CDECL Lib "libtom.dll" Alias "mp_reduce_is_2k" (ByRef a As mp_int) As Long
Declare Function mp_reduce_2k_setup CDECL Lib "libtom.dll" Alias "mp_reduce_2k_setup" (ByRef a As mp_int, ByRef d As Long) As Long
Declare Function mp_reduce_2k CDECL Lib "libtom.dll" Alias "mp_reduce_2k" (ByRef a As mp_int, ByRef n As mp_int, ByVal d As Long) As Long
Declare Function mp_reduce_is_2k_l CDECL Lib "libtom.dll" Alias "mp_reduce_is_2k_l" (ByRef a As mp_int) As Long
Declare Function mp_reduce_2k_setup_l CDECL Lib "libtom.dll" Alias "mp_reduce_2k_setup_l" (ByRef a As mp_int, ByRef d As mp_int) As Long
Declare Function mp_reduce_2k_l CDECL Lib "libtom.dll" Alias "mp_reduce_2k_l" (ByRef a As mp_int, ByRef n As mp_int, ByRef d As mp_int) As Long
Declare Function mp_exptmod CDECL Lib "libtom.dll" Alias "mp_exptmod" (ByRef a As mp_int, ByRef b As mp_int, ByRef c As mp_int, ByRef d As mp_int) as long
Declare Function mp_prime_is_divisible CDECL Lib "libtom.dll" Alias "mp_prime_is_divisible" (ByRef a As mp_int, ByRef result As Long) As Long
Declare Function mp_prime_fermat CDECL Lib "libtom.dll" Alias "mp_prime_fermat" (ByRef a As mp_int, ByRef b As mp_int, ByRef result As Long) As Long
Declare Function mp_prime_miller_rabin CDECL Lib "libtom.dll" Alias "mp_prime_miller_rabin" (ByRef a As mp_int, ByRef b As mp_int, ByRef result As Long) As Long
Declare Function mp_prime_rabin_miller_trials CDECL Lib "libtom.dll" Alias "mp_prime_rabin_miller_trials" (Size1 As Long) As Long
Declare Function mp_prime_is_prime CDECL Lib "libtom.dll" Alias "mp_prime_is_prime" (ByRef a As mp_int, t As Long, ByRef result As Long) As Long
Declare Function mp_prime_next_prime CDECL Lib "libtom.dll" Alias "mp_prime_next_prime" (ByRef a As mp_int, ByVal t As Long, ByVal bbs_style As Long) As Long
Declare Function mp_prime_random_ex CDECL Lib "libtom.dll" Alias "mp_prime_random_ex" (ByRef a As mp_int, ByVal t As Long, ByVal Size As Long, ByVal flags As Long, ByRef cb As DWord, ByVal dat As Any Ptr) As Long
Declare Function mp_count_bits CDECL Lib "libtom.dll" Alias "mp_count_bits" (ByRef a As mp_int) As Long
Declare Function mp_unsigned_bin_size CDECL Lib "libtom.dll" Alias "mp_unsigned_bin_size" (ByRef a As mp_int) As Long
Declare Function mp_read_unsigned_bin CDECL Lib "libtom.dll" Alias "mp_read_unsigned_bin" (ByRef a As mp_int, ByRef b As Byte, c As Long) As Long
Declare Function mp_to_unsigned_bin CDECL Lib "libtom.dll" Alias "mp_to_unsigned_bin" (ByRef a As mp_int, ByRef b As Byte) As Long
Declare Function mp_to_unsigned_bin_n CDECL Lib "libtom.dll" Alias "mp_to_unsigned_bin_n" (ByRef a As mp_int, ByRef b As Byte, ByRef outlen As Long) As Long
Declare Function mp_signed_bin_size CDECL Lib "libtom.dll" Alias "mp_signed_bin_size" (ByRef a As mp_int) As Long
Declare Function mp_read_signed_bin CDECL Lib "libtom.dll" Alias "mp_read_signed_bin" (ByRef a As mp_int, ByRef b As Byte, ByVal c As Long) As Long
Declare Function mp_to_signed_bin CDECL Lib "libtom.dll" Alias "mp_to_signed_bin" (ByRef a As mp_int, ByRef b As Byte) As Long
Declare Function mp_to_signed_bin_n CDECL Lib "libtom.dll" Alias "mp_to_signed_bin_n" (ByRef a As mp_int, ByRef b As Byte, ByRef outlen As Long) As Long
Declare Function mp_read_radix CDECL Lib "libtom.dll" Alias "mp_read_radix" (ByRef a As mp_int, ByVal s As String, ByVal radix As Long) As Long
Declare Function mp_toradix CDECL Lib "libtom.dll" Alias "mp_toradix" (ByRef a As mp_int, ByRef s As String, ByVal radix As Long) As Long
Declare Function mp_toradix_n CDECL Lib "libtom.dll" Alias "mp_toradix_n" (ByRef a As mp_int, ByRef s As String, radix As Long, ByVal maxlen As Long) As Long
Declare Function mp_radix_size CDECL Lib "libtom.dll" Alias "mp_radix_size" (ByRef a As mp_int, radix As Long, ByRef Size As Long) As Long
'the next two functions don't work
'Declare Function mp_fread CDECL Lib "libtom.dll" Alias "mp_fread" (ByRef a As mp_int, radix As Long, ByVal stream As Any Ptr) As Long
'Declare Function mp_fwrite CDECL Lib "libtom.dll" Alias "mp_fwrite" (ByRef a As mp_int, ByVal radix As Long, ByVal stream As any Ptr) As Long
Declare Function s_mp_add CDECL Lib "libtom.dll" Alias "s_mp_add" (ByRef a As mp_int, ByRef b As mp_int, ByRef c As mp_int) As Long
Declare Function s_mp_sub CDECL Lib "libtom.dll" Alias "s_mp_sub" (ByRef a As mp_int, ByRef b As mp_int, ByRef c As mp_int) As Long
Declare Function fast_s_mp_mul_digs CDECL Lib "libtom.dll" Alias "fast_s_mp_mul_digs" (ByRef a As mp_int, ByRef b As mp_int, ByRef c As mp_int, ByVal digs As Long) As Long
Declare Function s_mp_mul_digs CDECL Lib "libtom.dll" Alias "s_mp_mul_digs" (ByRef a As mp_int, ByRef b As mp_int, ByRef c As mp_int, digs As Long) As Long
Declare Function fast_s_mp_mul_high_digs CDECL Lib "libtom.dll" Alias "fast_s_mp_mul_high_digs" (ByRef a As mp_int, ByRef b As mp_int, ByRef c As mp_int, ByVal digs As Long) As Long
Declare Function s_mp_mul_high_digs CDECL Lib "libtom.dll" Alias "s_mp_mul_high_digs" (ByRef a As mp_int, ByRef b As mp_int, ByRef c As mp_int, digs As Long) As Long
Declare Function fast_s_mp_sqr CDECL Lib "libtom.dll" Alias "fast_s_mp_sqr" (ByRef a As mp_int, ByRef b As mp_int) As Long
Declare Function s_mp_sqr CDECL Lib "libtom.dll" Alias "s_mp_sqr" (ByRef a As mp_int, ByRef b As mp_int) As Long
Declare Function mp_karatsuba_mul CDECL Lib "libtom.dll" Alias "mp_karatsuba_mul" (ByRef a As mp_int, ByRef b As mp_int, ByRef c As mp_int) As Long
Declare Function mp_toom_mul CDECL Lib "libtom.dll" Alias "mp_toom_mul" (ByRef a As mp_int, ByRef b As mp_int, ByRef c As mp_int) As Long
Declare Function mp_karatsuba_sqr CDECL Lib "libtom.dll" Alias "mp_karatsuba_sqr" (ByRef a As mp_int, ByRef b As mp_int) As Long
Declare Function mp_toom_sqr CDECL Lib "libtom.dll" Alias "mp_toom_sqr" (ByRef a As mp_int, ByRef b As mp_int) As Long
Declare Function fast_mp_invmod CDECL Lib "libtom.dll" Alias "fast_mp_invmod" (ByRef a As mp_int, ByRef b As mp_int, ByRef c As mp_int) As Long
Declare Function mp_invmod_slow CDECL Lib "libtom.dll" Alias "mp_invmod_slow" (ByRef a As mp_int, ByRef b As mp_int, ByRef c As mp_int) As Long
Declare Function fast_mp_montgomery_reduce CDECL Lib "libtom.dll" Alias "fast_mp_montgomery_reduce" (ByRef a As mp_int, ByRef m As mp_int, ByVal mp As Long) As Long
Declare Function mp_exptmod_fast CDECL Lib "libtom.dll" Alias "mp_exptmod_fast" (ByRef G As mp_int, ByRef X As mp_int, ByRef P As mp_int, ByRef Y As mp_int, ByVal mode As Long) As Long
Declare Function s_mp_exptmod CDECL Lib "libtom.dll" Alias "s_mp_exptmod" (ByRef G As mp_int, ByRef X As mp_int, ByRef P As mp_int, ByRef Y As mp_int, ByVal mode As Long) As Long
Declare Sub bn_reverse CDECL Lib "libtom.dll" Alias "bn_reverse" (ByRef s As String, ByVal Len1 As Long)
Uses "console"
Dim i, j, k As mp_int
Dim s, s2 As Asciiz *11024
Dim lup As Long
s = "25998305698778882782694282216427520062325059925056858892956364318072249183875081684424630961752645071829620406259524052715060610486050318728348276382757621322537385844563410552297"
s = s&"03960182489849843615430088190470906264709925195692664930112398138571316164112551306702883093681147292350025702486270799158479897114054161730071234231202135809223242312655616315542"
s = s&"94858343807188790751402459010233773238407873247871862406989702271177063193217340225057994600159267813767262212104205783683630250951779202250748346696462525454084274493510695150600"
s = s&"97278605753619956900553867954076817448024435352255848859957690927310303677723596457787879480350715750825350328986324045895598243176085969044169791618738993283910620831103810475946"
s = s&"33049203806694209608683892867150595141099756215041900582804111939062007092622474933044811876158602334452145258026429850607093412457930099562830313117366885751915651353104749583302"
s = s&"15531787533896617511151902175564933090237349475682507288214834576209815927063905016273599569214838817459219798765924129592642265326108449655330560382382808271594777451322142493737"
s = s&"50436634764123083968071055694200079842493400807012422680542410393489626517468028967370112652092983565987174897956418497929373045550019576989200303483284173094578415208174108966111"
s = s&"65769767114391007120100420915169233837546621367856373302160998891694535450327805786016482732217698026063614406032639393593323756983641365852805399102913705624570668116080267832367"
s = s&"64726683132531914526690079457415699556325344231253602665256734457103448932253363180362275189980249038592241415696321784878512266463323578847913879046543862149605315487173265449103"
s = s&"44985254212880143267315626819963685160364936678345613170342983101939558616468939108822708875327843669816436591423630016096816579847927321181094384808489711445890318046103329755131"
s = s&"62952739089719888839081179410446068318437603084717680650172030192284372699875462519689409497103701529019146230799704955103121558571053162856032846963053023073895580770204846561803"
s = s&"19793653498159544887791694640438098310707665084132391468679417809075146524582340076967046467032663807608084498486090543541686857510467272349459625744971256146278089920197008015202"
s = s&"02690113820825817340003057701196678502919432716213170216770030043873909619982612504305878265633841170539161255126910093406488152402014905107844865504985975694570452768848049186511"
s = s&"99343974854638155380738541969317159047708071490994665030286091840214412215908967522889330586157041819473261044582655233984838954869758582863093426501294751819363488772591396849482"
s = s&"14541231696731536480114115069165287234606436467155715957870568873819933917795169659740301812765066254701635819988078720330945566076017124663839115674714319451320282844920088886274"
s = s&"73183080652614885161771855164380212565129787480664319435252412243109730118888371736549215790484028504236717022689894947667447117982384625105846406370847334996010683331030678681427"
s = s&"56427363881319487885330401465342823767881986629761083854935148599074348338648707137178894243135645129870888909362061936491534282424966231253781963484583313517427756831015160329084"
s = s&"60421876455141368075149317323870087337557877266063706878152841099564845544576025849122752684922700102768063842022852201618436041096969316122507106954031660961201152487601068885764"
s = s&"19087725518021013593600262995448253448543521153012842991260187150278738361140333399022055405953281564677515388599440587422064155578156817459134199947346374100959559692603359039655"
s = s&"24334122036308511201866709174269603063778755681701026350607067305932389961340795092328701602727982045965114355375309786443302187387677733514059550562299023733263296576813373658598"
s = s&"84155874806028591436772424316939960794574765085028914727655378379459371910837700308282017621308703102279516109620292854140593361925457498990624664484126521180443327638609256610715"
s = s&"82419939836634496774665279093978101639317890062004035158543041690432702567221611683434360955191759751176141733345322786732343897113347147010081549975643292804851441713936816718754"
s = s&"75203079259426309412509694297381930371443878319798964013436284657801174397785118092847511855767525967405542569731376220819573179017358826348414526450228259798198209358429448216351"
s = s&"87295580951120792676121655839110764857384570681249408390387336607185144639704928963678599968065764930847785365152347532233552576705584073135488835033287183224933798541691954594398"
s = s&"98333887079542214646235864356921050476220943937551133229566137714685998165093616730709543866077509213332725389374230923815844390925073374824071362988069361361011255967699497866661"
s = s&"62714841452877314930577231653669903532722035593269784295966890513044297239172109719876364689715311254024899745850588930498595823251631264631173564483117330017864990279267177572324"
s = s&"35656629842359245452820345956459909201496694299826694363861604887856263567748856093177664375222549588154447598478535276027080215208489307640259709395796603894282589230696206726925"
s = s&"56578816868263589345214720402757856535244008389116357181992863100461445950794646004645924711561995664374903749492728661653448592183668353072789614088833332061767578125"

s2 = "14953694418600598137797892976168196776550567060529797819121509629371302803543047947100026386030253936809331859893109397981441734931992474450663129199455045572910284842176406899012"
s2 = s2&"43307622714965754048859748977920315548552684814674994364164951139260855448178060157456685670415726352514465858604473206508032550589348599881678743369109149811460642052784089771422"
s2 = s2&"91744415137914234657570985630122391641558757994793525336676787152374526553521316997756026971178406162991176203118480489761094622115846192860175725211188264259166267492428995258110"
s2 = s2&"83683907649791133130877994971132411816207015370755703514028461716861110300326545169051323939067656566373301272620855075647555506321187475534683658318074908480834384731815036732634"
s2 = s2&"82858395516104456338345864555593262669916685657966382646844046866252988586196209737157516637209718863572931976654319891599277473185165878816845974781435780684185989999957487383831"
s2 = s2&"37861925308297636682237514758155596269988917999368638114799054174138930419001043614365097024322487136127353937477973446705732154671588371246649431940951731178168927368725123487729"
s2 = s2&"03771697996577386307417031230349886957523265128233630357733358656165643541869349027855435790150989362395180774169792155845865791329928242819582039416749235148627494709871544555020"
s2 = s2&"10093324654473516620475885269703536176341896090069366921600832763359675089171251343765236529648019050977560844310113870723363074154261375145861092865638405899047624663287724736360"
s2 = s2&"80476570473845749834946205966830068246068081055301618114115160260567957400406556226799051150155476897434294515025174020402128851623296484796653860254811329408845863084135782921536"
s2 = s2&"21483726866822491840720165305477713243852611546603949257573919201693347019306877933275222402190674678219165949517721242004971360669326466380830023692972980861068704768448043607886"
s2 = s2&"71423944136093456527786040949331054778122595410580450575629487259866067631083443206975004661365278327745764540671388719699149525390448071738778331668776093407133995815843944327218"
s2 = s2&"44665956342684071503071107022242837863889795149361395266882979889753442262605933142862525196227636432619247162948483815669265297033419502214095114217328465436045481752075057310608"
s2 = s2&"44137720865695818022430570333219854583320117700195969473115380643833520674709196440916318387310069492829393841228234955558630366974716594286601533756947679648847579611676791212434"
s2 = s2&"40028060803325441354945609819663260483975637672527300005951101097016242870505527019762222302185565802468710433554443789441694256848840008154289267824103969873333154288205338600609"
s2 = s2&"77842752054812402996259937871008789825718924504985019890927788235251272998474212768045082439287089460080388852001455593433597194810757462132468056513501635633081007257649483112682"
s2 = s2&"34822501637453283225820881849606453267653519474313200805526606359083453509438000385003910951061856642587227716696892881885276438012629059859421937780214247605390680174843587561946"
s2 = s2&"18314656471218118039863663105461283739860742984199751430980056375347609884716204802408420601758404838089035474738962736283217374264765883445306310888553952447712151286626105775549"
s2 = s2&"73952543853157493575398455081916020756387754825722911462995957383017698708383569724166635814416023587521247552730824708256637879634438550373052235144370852480099093802037072882646"
s2 = s2&"32614358321432421646474758581779379273787711138284057636642225697503641601929401639008102855704825605385587400170088108865486989656844307256957096459406069983892667934860590594212"
s2 = s2&"64207090035352881784015144399076714770706583186958602234705999155280559159818075169130946134849669862352857408492655215371517430222717010480652982755587164565554865565137968942281"
s2 = s2&"30585907963279591693153127385537915504305139241778224122264166888707590254339186101506086374607915696247286880300273718183576480051736136229327209786466661828280717095099432518258"
s2 = s2&"62112857275386877828198053625783207675184392555330989527083393662182134933588727503843287271421499880958129106541726815265795925097182446884331285888015088738822106103494604839411"
s2 = s2&"71935273403293012896725297262632231479350344860770189200228711727280744694520246536474683168581083789150032910734207493731481478817765652323081725837341371502685169550084905042551"
s2 = s2&"94968300754792052664802355492330949582901902540110000531949620448375823368348626374459486370104038386643463775570215027986887983173680297564514867086636686849893527912763767483845"
s2 = s2&"54870037178075416211081932500451458152686939788972837260816169766577003587059851122359323070088850008363994264651072287273196241809330233010117528732688007449247574878428548398386"
s2 = s2&"73206500345267401423739778376321951113447393076114319524366256754477382584302212545897813368138475067522929127800802677805576775240634181480490016951352798893453287748010286982821"
s2 = s2&"32388239449368378252259247675901904409790567434116208634661532264437633169790035015446526660783709640299285895702764613315509042135055117925041047687444744230328743205855947338429"
s2 = s2&"96027579206308099156305659536475366018471863849833694124608532854592685582553705477203558891515273967068330509324599307015184379886050781984586886687451347845490289934336"
mp_init(i) 'mp_init_size(i, 5120)
mp_init(j) 'mp_init_size(j, 5120)
mp_init(k) 'mp_init_size(k, 5120)
'mp_init_multi(i, j, k, 0)
mp_read_radix (i, s , 10)
mp_read_radix (j, s2, 10)
Dim StartTime As Double = Timer
For lup=1 To 10000
mp_mul (i, j, k)
Next
Dim ElapsedTime As Double
ElapsedTime = Timer-StartTime
mp_toradix (k, s, 10)
Console_WriteLine s
Console_WriteLine "ElapsedTime of 10000 iterations of mp_mul (i, j, k) = "&Str$(ElapsedTime)
Console_WriteLine Str$(Len(s))
Console_WriteLine "All done. Press any key to finish"
Console_WaitKey
'mp_clear_multi(i, j, k, 0)
mp_clear(k)
mp_clear(j)
mp_clear(i)

[danbaron]

OK, I have both of the pdf files, Johan.

I can see that tommath.pdf is very very good for learning about this subject.

Boy, it seems like he really did a good job with his entire implementation.

And, as you showed, libtom multiplies with real speed.

Maybe I can learn something.

[danbaron]

I have been playing around with trying to multiply big integers quickly.

One thing I noticed is that in most of the documentation about how to do it, the multiplication is done using base 2.

So, I thought that I need to be able to convert a base 10 string into base 2. And, I need to be able to convert a number in a base 2 register back into a base 10 string (presumably, people want their inputs and outputs in base 10).

If I am correct, a number in base 2, in which the digits are bit addressed, is exactly the same as a number in base 256, in which the the digits are byte addressed.

Below is C code which converts base 10 strings into base 256 byte registers, and back.

I must be missing a lot in my head, because, everything I try concerning big integers is so amazingly slow compared to for instance, libTom or Racket.

-----------------------------------------------

Anyway, I did find the problem of doing the conversions to be, not so straightforward.

For instance, say you have a 5000 character string representing a 5000 digit base 10 number,

"4396879584757..

The first character, '4', represents the number, 4 * 10^4999. If you think about it, you cannot use C to perform any mathematics on that number, it is too big.

-----------------------------------------------

I used Pelles C to do all of the coding. I cannot say even one bad thing about the Pelles C IDE.

When I got the code the way I wanted it, I used GCC for the final compilation. I have seen nothing that beats its execution speed.

You will notice that the conversion from base 10 to base 256, is a lot faster than the reverse conversion. It is basically because, 256 is bigger than 10.

The 5000 digit integer used in the code is equal to 1565^1565.

:evil: :twisted:


' code ------------------------------------------------------------------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>

//-------------------------------------------------------------------------------------------------------

#define short unsigned short int
#define long unsigned long int

#define maxdigits 10000
#define b10 10
#define b256 256

//-------------------------------------------------------------------------------------------------------

unsigned char reg[10][maxdigits];

//-------------------------------------------------------------------------------------------------------

char intval(char c)
{
return c - 48;
}

//-------------------------------------------------------------------------------------------------------

char charval(char c)
{
return c + 48;
}

//-------------------------------------------------------------------------------------------------------

void reversereg(long numdigits, unsigned char r[])
{
static unsigned char temp[maxdigits];
long i;
for(i=0; i < numdigits; i++) temp[numdigits - 1 - i] = r[i];
for(i=0; i < numdigits; i++) r[i] = temp[i];
}

//-------------------------------------------------------------------------------------------------------

long maxregpower(unsigned char r[])
{
long i;
for(i = 0; i < maxdigits; i++) if(r[maxdigits - 1 - i] > 0) break;
return maxdigits - i;
}

//-------------------------------------------------------------------------------------------------------

void copyregtostring(unsigned char r[], char* string)
{
long i;
long mp = maxregpower(r);
if(mp==0) string[0] = charval(0);
else
{
for(i = 0; i < mp; i++) string[i] = charval( r[i]);
}
string[mp + 1] = '\0';
}

//-------------------------------------------------------------------------------------------------------

void setreg(unsigned char r[], long index, unsigned char value)
{
r[index] = value;
}

//-------------------------------------------------------------------------------------------------------

void zeroreg(unsigned char r[])
{
memset(r, 0, maxdigits);
}

//-------------------------------------------------------------------------------------------------------

void addregs(short base, long numdigits, unsigned char r1[], unsigned char r2[], unsigned char r3[])
{
short sum;
long i;
unsigned char carry = 0;
for(i = 0; i < numdigits; i++)
{
sum = r1[i] + r2[i] + carry;
carry = sum / base;
r3[i] = sum % base;
}
}

//-------------------------------------------------------------------------------------------------------

void setregsequal(long numdigits, unsigned char r1[], unsigned char r2[])
{
memcpy(r1, r2, maxdigits);
}

//-------------------------------------------------------------------------------------------------------

void multregbydigit(short base, long numdigits, unsigned char r1[], unsigned char r2[], unsigned char digit, long shift)
{
static unsigned char temp[maxdigits];
short product;
long i;
unsigned char carry = 0;
zeroreg(temp);
for(i = 0; i < numdigits; i++)
{
product = r1[i] * digit + carry;
carry = product / base;
temp[i + shift] = product % base;
}
setregsequal(numdigits, r2, temp);
}

//-------------------------------------------------------------------------------------------------------

void multbase10regby256(long numdigits, unsigned char r[])
{
long i;
static unsigned char temp1[maxdigits];
static unsigned char temp2[maxdigits];
static unsigned char temp3[maxdigits];
zeroreg(temp3);
temp1[0] = 6;
temp1[1] = 5;
temp1[2] = 2;
for(i = 0; i < 3; i++)
{
multregbydigit(b10, numdigits, r, temp2, temp1[i], i);
addregs(b10, numdigits, temp2, temp3, temp3);
}
setregsequal(numdigits, r, temp3);
}

//-------------------------------------------------------------------------------------------------------

void multbase10regbybase256digit(long numdigits, unsigned char r1[], unsigned char r2[], unsigned char digit)
{
long i;
static unsigned char temp1[maxdigits];
static unsigned char temp2[maxdigits];
zeroreg(r2);
temp1[2] = digit / 100;
temp1[1] = (digit - temp1[2] * 100) / 10;
temp1[0] = digit - temp1[2] * 100 - temp1[1] * 10;
for(i = 0; i < 3; i++)
{
multregbydigit(b10, numdigits, r1, temp2, temp1[i], i);
addregs(b10, numdigits, r2, temp2, r2);
}
}

//-------------------------------------------------------------------------------------------------------

long numbase256digits(long numbase10digits)
{
return ceil(log(10)/log(256) * numbase10digits) + 1;
}

//-------------------------------------------------------------------------------------------------------

long numbase10digits(long numbase256digits)
{
return ceil(log(256)/log(10) * numbase256digits) + 3;
}

//-------------------------------------------------------------------------------------------------------

void base10stringtobase256reg(char* string, unsigned char r[])
{
long i, nb256digits;
static unsigned char power[maxdigits];
static unsigned char temp[maxdigits];
long nb10digits = strlen(string);

zeroreg(r);
zeroreg(temp);
zeroreg(power);
setreg(power, 0, 1);
for(i = 0; i < nb10digits; i++)
{
nb256digits = numbase256digits(i);
multregbydigit(b256, nb256digits, power, temp, intval(string[nb10digits - 1 - i]), 0);
addregs(b256, nb256digits, temp, r, r);
multregbydigit(b256, nb256digits, power, power, 10, 0);
}
}

//-------------------------------------------------------------------------------------------------------

void base256regtobase10string(unsigned char r[], char* string)
{
long i, nb10digits;
static unsigned char power[maxdigits];
static unsigned char temp1[maxdigits];
static unsigned char temp2[maxdigits];
long nb256digits = maxregpower(r);
zeroreg(temp1);
zeroreg(temp2);
zeroreg(power);
setreg(power, 0, 1);
for(i = 0; i < nb256digits; i++)
{
nb10digits = numbase10digits(i);
multbase10regbybase256digit(nb10digits, power, temp1, r[i]);
addregs(b10, nb10digits, temp1, temp2, temp2);
multbase10regby256(nb10digits, power);
}
nb10digits = maxregpower(temp2);
reversereg(nb10digits, temp2);
copyregtostring(temp2, string);
}

//-------------------------------------------------------------------------------------------------------

int main()
{
clock_t ticks1, ticks2, totalticks;
double seconds;
long maxchars = 10000;
char num1[maxchars];
char num2[maxchars];
char num3[maxchars];
char c;
long i;

strcpy(num1, "4294967295");

strcpy(num2, "\
2599830569877888278269428221642752006232505992505685889295636431807224918387508168442463096175264507\
1829620406259524052715060610486050318728348276382757621322537385844563410552297039601824898498436154\
3008819047090626470992519569266493011239813857131616411255130670288309368114729235002570248627079915\
8479897114054161730071234231202135809223242312655616315542948583438071887907514024590102337732384078\
7324787186240698970227117706319321734022505799460015926781376726221210420578368363025095177920225074\
8346696462525454084274493510695150600972786057536199569005538679540768174480244353522558488599576909\
2731030367772359645778787948035071575082535032898632404589559824317608596904416979161873899328391062\
0831103810475946330492038066942096086838928671505951410997562150419005828041119390620070926224749330\
4481187615860233445214525802642985060709341245793009956283031311736688575191565135310474958330215531\
7875338966175111519021755649330902373494756825072882148345762098159270639050162735995692148388174592\
1979876592412959264226532610844965533056038238280827159477745132214249373750436634764123083968071055\
6942000798424934008070124226805424103934896265174680289673701126520929835659871748979564184979293730\
4555001957698920030348328417309457841520817410896611165769767114391007120100420915169233837546621367\
8563733021609988916945354503278057860164827322176980260636144060326393935933237569836413658528053991\
0291370562457066811608026783236764726683132531914526690079457415699556325344231253602665256734457103\
4489322533631803622751899802490385922414156963217848785122664633235788479138790465438621496053154871\
7326544910344985254212880143267315626819963685160364936678345613170342983101939558616468939108822708\
8753278436698164365914236300160968165798479273211810943848084897114458903180461033297551316295273908\
9719888839081179410446068318437603084717680650172030192284372699875462519689409497103701529019146230\
7997049551031215585710531628560328469630530230738955807702048465618031979365349815954488779169464043\
8098310707665084132391468679417809075146524582340076967046467032663807608084498486090543541686857510\
4672723494596257449712561462780899201970080152020269011382082581734000305770119667850291943271621317\
0216770030043873909619982612504305878265633841170539161255126910093406488152402014905107844865504985\
9756945704527688480491865119934397485463815538073854196931715904770807149099466503028609184021441221\
5908967522889330586157041819473261044582655233984838954869758582863093426501294751819363488772591396\
8494821454123169673153648011411506916528723460643646715571595787056887381993391779516965974030181276\
5066254701635819988078720330945566076017124663839115674714319451320282844920088886274731830806526148\
8516177185516438021256512978748066431943525241224310973011888837173654921579048402850423671702268989\
4947667447117982384625105846406370847334996010683331030678681427564273638813194878853304014653428237\
6788198662976108385493514859907434833864870713717889424313564512987088890936206193649153428242496623\
1253781963484583313517427756831015160329084604218764551413680751493173238700873375578772660637068781\
5284109956484554457602584912275268492270010276806384202285220161843604109696931612250710695403166096\
1201152487601068885764190877255180210135936002629954482534485435211530128429912601871502787383611403\
3339902205540595328156467751538859944058742206415557815681745913419994734637410095955969260335903965\
5243341220363085112018667091742696030637787556817010263506070673059323899613407950923287016027279820\
4596511435537530978644330218738767773351405955056229902373326329657681337365859884155874806028591436\
7724243169399607945747650850289147276553783794593719108377003082820176213087031022795161096202928541\
4059336192545749899062466448412652118044332763860925661071582419939836634496774665279093978101639317\
8900620040351585430416904327025672216116834343609551917597511761417333453227867323438971133471470100\
8154997564329280485144171393681671875475203079259426309412509694297381930371443878319798964013436284\
6578011743977851180928475118557675259674055425697313762208195731790173588263484145264502282597981982\
0935842944821635187295580951120792676121655839110764857384570681249408390387336607185144639704928963\
6785999680657649308477853651523475322335525767055840731354888350332871832249337985416919545943989833\
3887079542214646235864356921050476220943937551133229566137714685998165093616730709543866077509213332\
7253893742309238158443909250733748240713629880693613610112559676994978666616271484145287731493057723\
1653669903532722035593269784295966890513044297239172109719876364689715311254024899745850588930498595\
8232516312646311735644831173300178649902792671775723243565662984235924545282034595645990920149669429\
9826694363861604887856263567748856093177664375222549588154447598478535276027080215208489307640259709\
3957966038942825892306962067269255657881686826358934521472040275785653524400838911635718199286310046\
1445950794646004645924711561995664374903749492728661653448592183668353072789614088833332061767578125");

printf("\nStart.\n\n");
printf("Test conversion of base 10 string (num1) to base 256 register.\n\n");
printf("Calculating base 256 representation of 4,294,967,295.\n\n");

base10stringtobase256reg(num1, reg[0]);
printf("Done.\n\n");
printf("It should be, 255 * 256^0 + 255 * 256^1 + 255 * 256^2 + 255 * 256^3.\n\n");

for(i = 0; i < 5; i++)printf("reg[0][%u] = %u\n", i, reg[0][i]);
printf("\n\n");

ticks1 = clock();
base10stringtobase256reg(num2, reg[0]);
ticks2 = clock();
totalticks = ticks2 - ticks1;
seconds = (double)totalticks / CLOCKS_PER_SEC;
printf("Time conversion of 5000 digit base 10 string (num2) into base 256 register.\n\n");
printf("CPU time = %0.3f seconds\n\n", seconds);

ticks1 = clock();
base256regtobase10string(reg[0], num3);
ticks2 = clock();
totalticks = ticks2 - ticks1;
seconds = (double)totalticks / CLOCKS_PER_SEC;
printf("Time conversion of base 256 register back into 5000 digit base 10 string (num3).\n\n");
printf("CPU time = %0.3f seconds\n\n", seconds);

printf("Check that num3 equals num2.\n\n");
printf("num3:\n\n");
printf("%s\n\n", num3);
printf("All done. Press 'Enter'.\n");

c = getchar();

return 0;
}

' output ----------------------------------------------------------------------------------------------------------------------------

C:\Users\root\Desktop\New C\mult>gcc main.c -O3 -o main.exe

C:\Users\root\Desktop\New C\mult>main

Start.

Test conversion of base 10 string (num1) to base 256 register.

Calculating base 256 representation of 4,294,967,295.

Done.

It should be, 255 * 256^0 + 255 * 256^1 + 255 * 256^2 + 255 * 256^3.

reg[0][0] = 255
reg[0][1] = 255
reg[0][2] = 255
reg[0][3] = 255
reg[0][4] = 0

Time conversion of 5000 digit base 10 string (num2) into base 256 register.

CPU time = 0.109 seconds

Time conversion of base 256 register back into 5000 digit base 10 string (num3).

CPU time = 1.030 seconds

Check that num3 equals num2.

num3:

25998305698778882782694282216427520062325059925056858892956364318072249183875081
68442463096175264507182962040625952405271506061048605031872834827638275762132253
73858445634105522970396018248984984361543008819047090626470992519569266493011239
81385713161641125513067028830936811472923500257024862707991584798971140541617300
71234231202135809223242312655616315542948583438071887907514024590102337732384078
73247871862406989702271177063193217340225057994600159267813767262212104205783683
63025095177920225074834669646252545408427449351069515060097278605753619956900553
86795407681744802443535225584885995769092731030367772359645778787948035071575082
53503289863240458955982431760859690441697916187389932839106208311038104759463304
92038066942096086838928671505951410997562150419005828041119390620070926224749330
44811876158602334452145258026429850607093412457930099562830313117366885751915651
35310474958330215531787533896617511151902175564933090237349475682507288214834576
20981592706390501627359956921483881745921979876592412959264226532610844965533056
03823828082715947774513221424937375043663476412308396807105569420007984249340080
70124226805424103934896265174680289673701126520929835659871748979564184979293730
45550019576989200303483284173094578415208174108966111657697671143910071201004209
15169233837546621367856373302160998891694535450327805786016482732217698026063614
40603263939359332375698364136585280539910291370562457066811608026783236764726683
13253191452669007945741569955632534423125360266525673445710344893225336318036227
51899802490385922414156963217848785122664633235788479138790465438621496053154871
73265449103449852542128801432673156268199636851603649366783456131703429831019395
58616468939108822708875327843669816436591423630016096816579847927321181094384808
48971144589031804610332975513162952739089719888839081179410446068318437603084717
68065017203019228437269987546251968940949710370152901914623079970495510312155857
10531628560328469630530230738955807702048465618031979365349815954488779169464043
80983107076650841323914686794178090751465245823400769670464670326638076080844984
86090543541686857510467272349459625744971256146278089920197008015202026901138208
25817340003057701196678502919432716213170216770030043873909619982612504305878265
63384117053916125512691009340648815240201490510784486550498597569457045276884804
91865119934397485463815538073854196931715904770807149099466503028609184021441221
59089675228893305861570418194732610445826552339848389548697585828630934265012947
51819363488772591396849482145412316967315364801141150691652872346064364671557159
57870568873819933917795169659740301812765066254701635819988078720330945566076017
12466383911567471431945132028284492008888627473183080652614885161771855164380212
56512978748066431943525241224310973011888837173654921579048402850423671702268989
49476674471179823846251058464063708473349960106833310306786814275642736388131948
78853304014653428237678819866297610838549351485990743483386487071371788942431356
45129870888909362061936491534282424966231253781963484583313517427756831015160329
08460421876455141368075149317323870087337557877266063706878152841099564845544576
02584912275268492270010276806384202285220161843604109696931612250710695403166096
12011524876010688857641908772551802101359360026299544825344854352115301284299126
01871502787383611403333990220554059532815646775153885994405874220641555781568174
59134199947346374100959559692603359039655243341220363085112018667091742696030637
78755681701026350607067305932389961340795092328701602727982045965114355375309786
44330218738767773351405955056229902373326329657681337365859884155874806028591436
77242431693996079457476508502891472765537837945937191083770030828201762130870310
22795161096202928541405933619254574989906246644841265211804433276386092566107158
24199398366344967746652790939781016393178900620040351585430416904327025672216116
83434360955191759751176141733345322786732343897113347147010081549975643292804851
44171393681671875475203079259426309412509694297381930371443878319798964013436284
65780117439778511809284751185576752596740554256973137622081957317901735882634841
45264502282597981982093584294482163518729558095112079267612165583911076485738457
06812494083903873366071851446397049289636785999680657649308477853651523475322335
52576705584073135488835033287183224933798541691954594398983338870795422146462358
64356921050476220943937551133229566137714685998165093616730709543866077509213332
72538937423092381584439092507337482407136298806936136101125596769949786666162714
84145287731493057723165366990353272203559326978429596689051304429723917210971987
63646897153112540248997458505889304985958232516312646311735644831173300178649902
79267177572324356566298423592454528203459564599092014966942998266943638616048878
56263567748856093177664375222549588154447598478535276027080215208489307640259709
39579660389428258923069620672692556578816868263589345214720402757856535244008389
11635718199286310046144595079464600464592471156199566437490374949272866165344859
2183668353072789614088833332061767578125

All done. Press 'Enter'.

[danbaron]

From last post.

"You will notice that the conversion from base 10 to base 256, is a lot faster than the reverse conversion. It is basically because, 256 is bigger than 10."

I fixed it (as best as I could).


' code ------------------------------------------------------------------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>

//-------------------------------------------------------------------------------------------------------

#define short unsigned short int
#define long unsigned long int

#define maxdigits 10000
#define b10 10
#define b256 256

//-------------------------------------------------------------------------------------------------------

unsigned char reg[10][maxdigits];

//-------------------------------------------------------------------------------------------------------

char intval(char c)
{
return c - 48;
}

//-------------------------------------------------------------------------------------------------------

char charval(char c)
{
return c + 48;
}

//-------------------------------------------------------------------------------------------------------

long maxregpower(unsigned char r[])
{
long i;
for(i = 0; i < maxdigits; i++) if(r[maxdigits - 1 - i] > 0) break;
return maxdigits - 1 - i;
}

//-------------------------------------------------------------------------------------------------------

void reversecopyregtostring(unsigned char r[], char* string)
{
long i;
long mp = maxregpower(r);
if(mp==0) string[0] = charval(0);
else
{
for(i = 0; i <= mp; i++) string[i] = charval( r[mp - i]);
}
string[mp + 1] = '\0';
}

//-------------------------------------------------------------------------------------------------------

void setreg(unsigned char r[], long index, unsigned char value)
{
r[index] = value;
}

//-------------------------------------------------------------------------------------------------------

void zeroreg(unsigned char r[])
{
memset(r, 0, maxdigits);
}

//-------------------------------------------------------------------------------------------------------

void addregs(short base, long numdigits, unsigned char r1[], unsigned char r2[], unsigned char r3[])
{
short sum;
long i;
unsigned char carry = 0;
for(i = 0; i < numdigits; i++)
{
sum = r1[i] + r2[i] + carry;
carry = sum / base;
r3[i] = sum % base;
}
}

//-------------------------------------------------------------------------------------------------------

void setregsequal(long numdigits, unsigned char r1[], unsigned char r2[])
{
memcpy(r1, r2, maxdigits);
}

//-------------------------------------------------------------------------------------------------------

void multregbydigit(short base, long numdigits, unsigned char r1[], unsigned char r2[], unsigned char digit, long shift)
{
static unsigned char temp[maxdigits];
short product;
long i;
unsigned char carry = 0;
zeroreg(temp);
for(i = 0; i < numdigits; i++)
{
product = r1[i] * digit + carry;
carry = product / base;
temp[i + shift] = product % base;
}
setregsequal(numdigits, r2, temp);
}

//-------------------------------------------------------------------------------------------------------

void multbase10regbybase256digit(long numdigits, unsigned char r1[], unsigned char r2[], short digit)
{
short product, sum, csum;
long i, j, k;
unsigned char carry = 0;
static unsigned char c[4][4];
for(i = 0; i < numdigits; i++)
{
product = r1[i] * digit;
sum = product + carry;
for(j = 3; j > 0; j--)
for(k = 0; k < 4; k++) c[j][k] = c[j - 1][k];
c[0][3] = sum / 1000;
c[0][2] = (sum - c[0][3] * 1000) / 100;
c[0][1] = (sum - c[0][3] * 1000 - c[0][2] * 100) / 10;
c[0][0] = sum - c[0][3] * 1000 - c[0][2] * 100 - c[0][1] * 10;
csum = 0;
for(j = 0; j < 4; j++) csum += c[j][j];
carry = csum / 10;
r2[i] = csum % 10;
}
}

//-------------------------------------------------------------------------------------------------------

long numbase256digits(long numbase10digits)
{
return ceil(log(10)/log(256) * numbase10digits) + 1;
}

//-------------------------------------------------------------------------------------------------------

long numbase10digits(long numbase256digits)
{
return ceil(log(256)/log(10) * numbase256digits) + 3;
}

//-------------------------------------------------------------------------------------------------------

void base10stringtobase256reg(char* string, unsigned char r[])
{
long i, nb256digits;
static unsigned char power[maxdigits];
static unsigned char temp[maxdigits];
long nb10digits = strlen(string);

zeroreg(r);
zeroreg(temp);
zeroreg(power);
setreg(power, 0, 1);
for(i = 0; i < nb10digits; i++)
{
nb256digits = numbase256digits(i);
multregbydigit(b256, nb256digits, power, temp, intval(string[nb10digits - 1 - i]), 0);
addregs(b256, nb256digits, temp, r, r);
multregbydigit(b256, nb256digits, power, power, 10, 0);
}
}

//-------------------------------------------------------------------------------------------------------

void base256regtobase10string(unsigned char r[], char* string)
{
long i, nb10digits;
static unsigned char power[maxdigits];
static unsigned char temp1[maxdigits];
static unsigned char temp2[maxdigits];
long nb256digits = maxregpower(r) + 1;
zeroreg(temp1);
zeroreg(temp2);
zeroreg(power);
setreg(power, 0, 1);
for(i = 0; i < nb256digits; i++)
{
nb10digits = numbase10digits(i);
multbase10regbybase256digit(nb10digits, power, temp1, r[i]);
addregs(b10, nb10digits, temp1, temp2, temp2);
multbase10regbybase256digit(nb10digits, power, power, b256);
}
nb10digits = maxregpower(temp2) + 1;
reversecopyregtostring(temp2, string);
}

//-------------------------------------------------------------------------------------------------------

int main()
{
clock_t ticks1, ticks2, ticks3, ticks4, totalticks;
double seconds;
long maxchars = 10000;
char num1[maxchars];
char num2[maxchars];
char num3[maxchars];
char c;
long i;

strcpy(num1, "4294967295");

strcpy(num2, "\
2599830569877888278269428221642752006232505992505685889295636431807224918387508168442463096175264507\
1829620406259524052715060610486050318728348276382757621322537385844563410552297039601824898498436154\
3008819047090626470992519569266493011239813857131616411255130670288309368114729235002570248627079915\
8479897114054161730071234231202135809223242312655616315542948583438071887907514024590102337732384078\
7324787186240698970227117706319321734022505799460015926781376726221210420578368363025095177920225074\
8346696462525454084274493510695150600972786057536199569005538679540768174480244353522558488599576909\
2731030367772359645778787948035071575082535032898632404589559824317608596904416979161873899328391062\
0831103810475946330492038066942096086838928671505951410997562150419005828041119390620070926224749330\
4481187615860233445214525802642985060709341245793009956283031311736688575191565135310474958330215531\
7875338966175111519021755649330902373494756825072882148345762098159270639050162735995692148388174592\
1979876592412959264226532610844965533056038238280827159477745132214249373750436634764123083968071055\
6942000798424934008070124226805424103934896265174680289673701126520929835659871748979564184979293730\
4555001957698920030348328417309457841520817410896611165769767114391007120100420915169233837546621367\
8563733021609988916945354503278057860164827322176980260636144060326393935933237569836413658528053991\
0291370562457066811608026783236764726683132531914526690079457415699556325344231253602665256734457103\
4489322533631803622751899802490385922414156963217848785122664633235788479138790465438621496053154871\
7326544910344985254212880143267315626819963685160364936678345613170342983101939558616468939108822708\
8753278436698164365914236300160968165798479273211810943848084897114458903180461033297551316295273908\
9719888839081179410446068318437603084717680650172030192284372699875462519689409497103701529019146230\
7997049551031215585710531628560328469630530230738955807702048465618031979365349815954488779169464043\
8098310707665084132391468679417809075146524582340076967046467032663807608084498486090543541686857510\
4672723494596257449712561462780899201970080152020269011382082581734000305770119667850291943271621317\
0216770030043873909619982612504305878265633841170539161255126910093406488152402014905107844865504985\
9756945704527688480491865119934397485463815538073854196931715904770807149099466503028609184021441221\
5908967522889330586157041819473261044582655233984838954869758582863093426501294751819363488772591396\
8494821454123169673153648011411506916528723460643646715571595787056887381993391779516965974030181276\
5066254701635819988078720330945566076017124663839115674714319451320282844920088886274731830806526148\
8516177185516438021256512978748066431943525241224310973011888837173654921579048402850423671702268989\
4947667447117982384625105846406370847334996010683331030678681427564273638813194878853304014653428237\
6788198662976108385493514859907434833864870713717889424313564512987088890936206193649153428242496623\
1253781963484583313517427756831015160329084604218764551413680751493173238700873375578772660637068781\
5284109956484554457602584912275268492270010276806384202285220161843604109696931612250710695403166096\
1201152487601068885764190877255180210135936002629954482534485435211530128429912601871502787383611403\
3339902205540595328156467751538859944058742206415557815681745913419994734637410095955969260335903965\
5243341220363085112018667091742696030637787556817010263506070673059323899613407950923287016027279820\
4596511435537530978644330218738767773351405955056229902373326329657681337365859884155874806028591436\
7724243169399607945747650850289147276553783794593719108377003082820176213087031022795161096202928541\
4059336192545749899062466448412652118044332763860925661071582419939836634496774665279093978101639317\
8900620040351585430416904327025672216116834343609551917597511761417333453227867323438971133471470100\
8154997564329280485144171393681671875475203079259426309412509694297381930371443878319798964013436284\
6578011743977851180928475118557675259674055425697313762208195731790173588263484145264502282597981982\
0935842944821635187295580951120792676121655839110764857384570681249408390387336607185144639704928963\
6785999680657649308477853651523475322335525767055840731354888350332871832249337985416919545943989833\
3887079542214646235864356921050476220943937551133229566137714685998165093616730709543866077509213332\
7253893742309238158443909250733748240713629880693613610112559676994978666616271484145287731493057723\
1653669903532722035593269784295966890513044297239172109719876364689715311254024899745850588930498595\
8232516312646311735644831173300178649902792671775723243565662984235924545282034595645990920149669429\
9826694363861604887856263567748856093177664375222549588154447598478535276027080215208489307640259709\
3957966038942825892306962067269255657881686826358934521472040275785653524400838911635718199286310046\
1445950794646004645924711561995664374903749492728661653448592183668353072789614088833332061767578125");

printf("\nStart.\n\n");
printf("Test conversion of base 10 string (num1) to base 256 register.\n\n");
printf("Calculating base 256 representation of 4,294,967,295.\n\n");

base10stringtobase256reg(num1, reg[0]);
printf("Done.\n\n");
printf("It should be, 255 * 256^0 + 255 * 256^1 + 255 * 256^2 + 255 * 256^3.\n\n");

for(i = 0; i < 5; i++)printf("reg[0][%u] = %u\n", i, reg[0][i]);
printf("\n\n");

ticks1 = clock();
base10stringtobase256reg(num2, reg[0]);
ticks2 = clock();
totalticks = ticks2 - ticks1;
seconds = (double)totalticks / CLOCKS_PER_SEC;
printf("Time conversion of 5000 digit base 10 string (num2) into base 256 register.\n\n");
printf("CPU time = %0.3f seconds\n\n", seconds);

ticks3 = clock();
base256regtobase10string(reg[0], num3);
ticks4 = clock();
totalticks = ticks4 - ticks3;
seconds = (double)totalticks / CLOCKS_PER_SEC;
printf("Time conversion of base 256 register back into 5000 digit base 10 string (num3).\n\n");
printf("CPU time = %0.3f seconds\n\n", seconds);

printf("Check that num3 equals num2.\n\n");
printf("num3:\n\n");
printf("%s\n\n", num3);

totalticks = ticks4 - ticks1;
seconds = (double)totalticks / CLOCKS_PER_SEC;
printf("Total time for conversion of 5000 digit base 10 string into base 256 register,\n");
printf("and back into base 10 string.\n\n");
printf("CPU time = %0.3f seconds\n\n", seconds);

printf("All done. Press 'Enter'.\n");

c = getchar();

return 0;
}

' output ----------------------------------------------------------------------------------------------------------------------------

C:\Users\root\Desktop\New C\mult>gcc main.c -O3 -o main.exe

C:\Users\root\Desktop\New C\mult>main

Start.

Test conversion of base 10 string (num1) to base 256 register.

Calculating base 256 representation of 4,294,967,295.

Done.

It should be, 255 * 256^0 + 255 * 256^1 + 255 * 256^2 + 255 * 256^3.

reg[0][0] = 255
reg[0][1] = 255
reg[0][2] = 255
reg[0][3] = 255
reg[0][4] = 0

Time conversion of 5000 digit base 10 string (num2) into base 256 register.

CPU time = 0.093 seconds

Time conversion of base 256 register back into 5000 digit base 10 string (num3).

CPU time = 0.640 seconds

Check that num3 equals num2.

num3:

25998305698778882782694282216427520062325059925056858892956364318072249183875081
68442463096175264507182962040625952405271506061048605031872834827638275762132253
73858445634105522970396018248984984361543008819047090626470992519569266493011239
81385713161641125513067028830936811472923500257024862707991584798971140541617300
71234231202135809223242312655616315542948583438071887907514024590102337732384078
73247871862406989702271177063193217340225057994600159267813767262212104205783683
63025095177920225074834669646252545408427449351069515060097278605753619956900553
86795407681744802443535225584885995769092731030367772359645778787948035071575082
53503289863240458955982431760859690441697916187389932839106208311038104759463304
92038066942096086838928671505951410997562150419005828041119390620070926224749330
44811876158602334452145258026429850607093412457930099562830313117366885751915651
35310474958330215531787533896617511151902175564933090237349475682507288214834576
20981592706390501627359956921483881745921979876592412959264226532610844965533056
03823828082715947774513221424937375043663476412308396807105569420007984249340080
70124226805424103934896265174680289673701126520929835659871748979564184979293730
45550019576989200303483284173094578415208174108966111657697671143910071201004209
15169233837546621367856373302160998891694535450327805786016482732217698026063614
40603263939359332375698364136585280539910291370562457066811608026783236764726683
13253191452669007945741569955632534423125360266525673445710344893225336318036227
51899802490385922414156963217848785122664633235788479138790465438621496053154871
73265449103449852542128801432673156268199636851603649366783456131703429831019395
58616468939108822708875327843669816436591423630016096816579847927321181094384808
48971144589031804610332975513162952739089719888839081179410446068318437603084717
68065017203019228437269987546251968940949710370152901914623079970495510312155857
10531628560328469630530230738955807702048465618031979365349815954488779169464043
80983107076650841323914686794178090751465245823400769670464670326638076080844984
86090543541686857510467272349459625744971256146278089920197008015202026901138208
25817340003057701196678502919432716213170216770030043873909619982612504305878265
63384117053916125512691009340648815240201490510784486550498597569457045276884804
91865119934397485463815538073854196931715904770807149099466503028609184021441221
59089675228893305861570418194732610445826552339848389548697585828630934265012947
51819363488772591396849482145412316967315364801141150691652872346064364671557159
57870568873819933917795169659740301812765066254701635819988078720330945566076017
12466383911567471431945132028284492008888627473183080652614885161771855164380212
56512978748066431943525241224310973011888837173654921579048402850423671702268989
49476674471179823846251058464063708473349960106833310306786814275642736388131948
78853304014653428237678819866297610838549351485990743483386487071371788942431356
45129870888909362061936491534282424966231253781963484583313517427756831015160329
08460421876455141368075149317323870087337557877266063706878152841099564845544576
02584912275268492270010276806384202285220161843604109696931612250710695403166096
12011524876010688857641908772551802101359360026299544825344854352115301284299126
01871502787383611403333990220554059532815646775153885994405874220641555781568174
59134199947346374100959559692603359039655243341220363085112018667091742696030637
78755681701026350607067305932389961340795092328701602727982045965114355375309786
44330218738767773351405955056229902373326329657681337365859884155874806028591436
77242431693996079457476508502891472765537837945937191083770030828201762130870310
22795161096202928541405933619254574989906246644841265211804433276386092566107158
24199398366344967746652790939781016393178900620040351585430416904327025672216116
83434360955191759751176141733345322786732343897113347147010081549975643292804851
44171393681671875475203079259426309412509694297381930371443878319798964013436284
65780117439778511809284751185576752596740554256973137622081957317901735882634841
45264502282597981982093584294482163518729558095112079267612165583911076485738457
06812494083903873366071851446397049289636785999680657649308477853651523475322335
52576705584073135488835033287183224933798541691954594398983338870795422146462358
64356921050476220943937551133229566137714685998165093616730709543866077509213332
72538937423092381584439092507337482407136298806936136101125596769949786666162714
84145287731493057723165366990353272203559326978429596689051304429723917210971987
63646897153112540248997458505889304985958232516312646311735644831173300178649902
79267177572324356566298423592454528203459564599092014966942998266943638616048878
56263567748856093177664375222549588154447598478535276027080215208489307640259709
39579660389428258923069620672692556578816868263589345214720402757856535244008389
11635718199286310046144595079464600464592471156199566437490374949272866165344859
2183668353072789614088833332061767578125

Total time for conversion of 5000 digit base 10 string into base 256 register,
and back into base 10 string.

CPU time = 0.733 seconds

All done. Press 'Enter'.

[danbaron]

I want to start trying to implement the Toom-Cook algorithm for multiplication of big integers.

http://en.wikipedia.org/wiki/Toom%E2%80%93Cook_multiplication

But, that will take a while to do, so, in order to get some immediate gratification, I decided to do something else now.

Below is exactly the same program that I made above, except that instead of converting a base 10 numeric string to a base 256 register and back, it converts the same base 10 numeric string to a base 65536 register and back. It is faster.


' code ------------------------------------------------------------------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>

//-------------------------------------------------------------------------------------------------------

#define long unsigned long int

#define maxdigits 10000
#define b10 10
#define b65536 65536

//-------------------------------------------------------------------------------------------------------

long reg[10][maxdigits];

//-------------------------------------------------------------------------------------------------------

char* makestring(char buffer[])
{
char* dummy;
long stringlength = strlen(buffer);
dummy = malloc(stringlength + 1);
memcpy(dummy, buffer, stringlength + 1);
return dummy;
}
//-------------------------------------------------------------------------------------------------------

char* makeemptystring(long numchars)
{
char* dummy;
dummy = malloc(numchars);
return dummy;
}

//-------------------------------------------------------------------------------------------------------

char getstringchar(char* s, long i)
{
return *(s + i);
}
//-------------------------------------------------------------------------------------------------------

char intval(char c)
{
return c - 48;
}

//-------------------------------------------------------------------------------------------------------

char charval(char c)
{
return c + 48;
}

//-------------------------------------------------------------------------------------------------------

long maxregpower(long r[])
{
long i;
for(i = 0; i < maxdigits; i++) if(r[maxdigits - 1 - i] > 0) break;
return maxdigits - 1 - i;
}

//-------------------------------------------------------------------------------------------------------

void reversecopyregtostring(long r[], char* string)
{
long i;
long mp = maxregpower(r);
if(mp==0) string[0] = charval(0);
else
{
for(i = 0; i <= mp; i++) string[i] = charval( r[mp - i]);
}
string[mp + 1] = '\0';
}

//-------------------------------------------------------------------------------------------------------

void setreg(long r[], long index, long value)
{
r[index] = value;
}

//-------------------------------------------------------------------------------------------------------

void zeroreg(long r[])
{
memset(r, 0, maxdigits);
}

//-------------------------------------------------------------------------------------------------------

void addregs(long base, long numdigits, long r1[], long r2[], long r3[])
{
long sum;
long i;
long carry = 0;
for(i = 0; i < numdigits; i++)
{
sum = r1[i] + r2[i] + carry;
carry = sum / base;
r3[i] = sum % base;
}
}

//-------------------------------------------------------------------------------------------------------

void setregsequal(long numdigits, long r1[], long r2[])
{
memcpy(r1, r2, maxdigits);
}

//-------------------------------------------------------------------------------------------------------

void multregbydigit(long base, long numdigits, long r1[], long r2[], long digit, long shift)
{
static long temp[maxdigits];
long product;
long i;
long carry = 0;
zeroreg(temp);
for(i = 0; i < numdigits; i++)
{
product = r1[i] * digit + carry;
carry = product / base;
temp[i + shift] = product % base;
}
setregsequal(numdigits, r2, temp);
}

//-------------------------------------------------------------------------------------------------------

void multbase10regbybase65536digit(long numdigits, long r1[], long r2[], long digit)
{
long product, sum, csum;
long c10, c100, c1000, c10000, c100000;
long i, j, k;
long carry = 0;
static long c[6][6];
for(i = 0; i < numdigits; i++)
{
product = r1[i] * digit;
sum = product + carry;
for(j = 5; j > 0; j--)
for(k = 0; k < 6; k++) c[j][k] = c[j-1][k];
c[0][5] = sum / 100000;
c100000 = c[0][5] * 100000;
c[0][4] = (sum - c100000) / 10000;
c10000 = c[0][4] * 10000;
c[0][3] = (sum - c100000 - c10000) / 1000;
c1000 = c[0][3] * 1000;
c[0][2] = (sum - c100000 - c10000 - c1000) / 100;
c100 = c[0][2] * 100;
c[0][1] = (sum - c100000 - c10000 - c1000 - c100) / 10;
c10 = c[0][1] * 10;
c[0][0] = sum - c100000 - c10000 - c1000 - c100 - c10;
csum = 0;
for(j = 0; j < 6; j++) csum += c[j][j];
carry = csum / 10;
r2[i] = csum % 10;
}
}

//-------------------------------------------------------------------------------------------------------

long numbase65536digits(long numbase10digits)
{
return ceil(log(10)/log(65536) * numbase10digits) + 1;
}
//-------------------------------------------------------------------------------------------------------

long numbase10digits(long numbase65536digits)
{
return ceil(log(65536)/log(10) * numbase65536digits) + 5;
}

//-------------------------------------------------------------------------------------------------------

void base10stringtobase65536reg(char* string, long r[])
{
long i, nb65536digits;
static long power[maxdigits];
static long temp[maxdigits];
long nb10digits = strlen(string);

zeroreg(r);
zeroreg(temp);
zeroreg(power);
setreg(power, 0, 1);
for(i = 0; i < nb10digits; i++)
{
nb65536digits = numbase65536digits(i);
multregbydigit(b65536, nb65536digits, power, temp, intval(getstringchar(string, nb10digits - 1 - i)), 0);
addregs(b65536, nb65536digits, temp, r, r);
multregbydigit(b65536, nb65536digits, power, power, 10, 0);
}
}

//-------------------------------------------------------------------------------------------------------

char* base65536regtobase10string(long r[])
{
long i, nb10digits;
char* dummy;
static long power[maxdigits];
static long temp1[maxdigits];
static long temp2[maxdigits];
long nb65536digits = maxregpower(r) + 1;
zeroreg(temp1);
zeroreg(temp2);
zeroreg(power);
setreg(power, 0, 1);
for(i = 0; i < nb65536digits; i++)
{
nb10digits = numbase10digits(i);
multbase10regbybase65536digit(nb10digits, power, temp1, r[i]);
addregs(b10, nb10digits, temp1, temp2, temp2);
multbase10regbybase65536digit(nb10digits, power, power, b65536);
}
nb10digits = maxregpower(temp2) + 1;
dummy = makeemptystring(nb10digits + 2);
reversecopyregtostring(temp2, dummy);
return dummy;
}

//-------------------------------------------------------------------------------------------------------

int main()
{
clock_t ticks1, ticks2, ticks3, ticks4, totalticks;
double seconds;
long maxchars = 10000;
char numbuffer[maxchars];
char* num1;
char* num2;
char* num3 = NULL;
char c;
long i;

strcpy(numbuffer, "4294967295");
num1 = makestring(numbuffer);

strcpy(numbuffer, "\
2599830569877888278269428221642752006232505992505685889295636431807224918387508168442463096175264507\
1829620406259524052715060610486050318728348276382757621322537385844563410552297039601824898498436154\
3008819047090626470992519569266493011239813857131616411255130670288309368114729235002570248627079915\
8479897114054161730071234231202135809223242312655616315542948583438071887907514024590102337732384078\
7324787186240698970227117706319321734022505799460015926781376726221210420578368363025095177920225074\
8346696462525454084274493510695150600972786057536199569005538679540768174480244353522558488599576909\
2731030367772359645778787948035071575082535032898632404589559824317608596904416979161873899328391062\
0831103810475946330492038066942096086838928671505951410997562150419005828041119390620070926224749330\
4481187615860233445214525802642985060709341245793009956283031311736688575191565135310474958330215531\
7875338966175111519021755649330902373494756825072882148345762098159270639050162735995692148388174592\
1979876592412959264226532610844965533056038238280827159477745132214249373750436634764123083968071055\
6942000798424934008070124226805424103934896265174680289673701126520929835659871748979564184979293730\
4555001957698920030348328417309457841520817410896611165769767114391007120100420915169233837546621367\
8563733021609988916945354503278057860164827322176980260636144060326393935933237569836413658528053991\
0291370562457066811608026783236764726683132531914526690079457415699556325344231253602665256734457103\
4489322533631803622751899802490385922414156963217848785122664633235788479138790465438621496053154871\
7326544910344985254212880143267315626819963685160364936678345613170342983101939558616468939108822708\
8753278436698164365914236300160968165798479273211810943848084897114458903180461033297551316295273908\
9719888839081179410446068318437603084717680650172030192284372699875462519689409497103701529019146230\
7997049551031215585710531628560328469630530230738955807702048465618031979365349815954488779169464043\
8098310707665084132391468679417809075146524582340076967046467032663807608084498486090543541686857510\
4672723494596257449712561462780899201970080152020269011382082581734000305770119667850291943271621317\
0216770030043873909619982612504305878265633841170539161255126910093406488152402014905107844865504985\
9756945704527688480491865119934397485463815538073854196931715904770807149099466503028609184021441221\
5908967522889330586157041819473261044582655233984838954869758582863093426501294751819363488772591396\
8494821454123169673153648011411506916528723460643646715571595787056887381993391779516965974030181276\
5066254701635819988078720330945566076017124663839115674714319451320282844920088886274731830806526148\
8516177185516438021256512978748066431943525241224310973011888837173654921579048402850423671702268989\
4947667447117982384625105846406370847334996010683331030678681427564273638813194878853304014653428237\
6788198662976108385493514859907434833864870713717889424313564512987088890936206193649153428242496623\
1253781963484583313517427756831015160329084604218764551413680751493173238700873375578772660637068781\
5284109956484554457602584912275268492270010276806384202285220161843604109696931612250710695403166096\
1201152487601068885764190877255180210135936002629954482534485435211530128429912601871502787383611403\
3339902205540595328156467751538859944058742206415557815681745913419994734637410095955969260335903965\
5243341220363085112018667091742696030637787556817010263506070673059323899613407950923287016027279820\
4596511435537530978644330218738767773351405955056229902373326329657681337365859884155874806028591436\
7724243169399607945747650850289147276553783794593719108377003082820176213087031022795161096202928541\
4059336192545749899062466448412652118044332763860925661071582419939836634496774665279093978101639317\
8900620040351585430416904327025672216116834343609551917597511761417333453227867323438971133471470100\
8154997564329280485144171393681671875475203079259426309412509694297381930371443878319798964013436284\
6578011743977851180928475118557675259674055425697313762208195731790173588263484145264502282597981982\
0935842944821635187295580951120792676121655839110764857384570681249408390387336607185144639704928963\
6785999680657649308477853651523475322335525767055840731354888350332871832249337985416919545943989833\
3887079542214646235864356921050476220943937551133229566137714685998165093616730709543866077509213332\
7253893742309238158443909250733748240713629880693613610112559676994978666616271484145287731493057723\
1653669903532722035593269784295966890513044297239172109719876364689715311254024899745850588930498595\
8232516312646311735644831173300178649902792671775723243565662984235924545282034595645990920149669429\
9826694363861604887856263567748856093177664375222549588154447598478535276027080215208489307640259709\
3957966038942825892306962067269255657881686826358934521472040275785653524400838911635718199286310046\
1445950794646004645924711561995664374903749492728661653448592183668353072789614088833332061767578125");

num2 = makestring(numbuffer);

printf("\nStart.\n\n");
printf("Test conversion of base 10 string (num1) to base 65536 register.\n\n");
printf("Calculating base 65536 representation of 4,294,967,295.\n\n");

base10stringtobase65536reg(num1, reg[0]);
printf("Done.\n\n");
printf("It should be, 65535 * 65536^0 + 65535 * 65536^1.\n\n");

for(i = 0; i < 3; i++)printf("reg[0][%u] = %u\n", i, reg[0][i]);
printf("\n\n");

ticks1 = clock();
base10stringtobase65536reg(num2, reg[0]);
ticks2 = clock();
totalticks = ticks2 - ticks1;
seconds = (double)totalticks / CLOCKS_PER_SEC;
printf("Time conversion of 5000 digit base 10 string (num2) into base 65536 register.\n\n");
printf("CPU time = %0.3f seconds\n\n", seconds);

ticks3 = clock();
num3 = base65536regtobase10string(reg[0]);
ticks4 = clock();
totalticks = ticks4 - ticks3;
seconds = (double)totalticks / CLOCKS_PER_SEC;
printf("Time conversion of base 65536 register back into 5000 digit base 10 string (num3).\n\n");
printf("CPU time = %0.3f seconds\n\n", seconds);

printf("Check that num3 equals num2.\n\n");
printf("num3:\n\n");
printf("%s\n\n", num3);

totalticks = ticks4 - ticks1;
seconds = (double)totalticks / CLOCKS_PER_SEC;
printf("Total time for conversion of 5000 digit base 10 string into base 65536 register,\n");
printf("and back into base 10 string.\n\n");
printf("CPU time = %0.3f seconds\n\n", seconds);

printf("All done. Press 'Enter'.\n");

c = getchar();

return 0;
}

' output ----------------------------------------------------------------------------------------------------------------------------

C:\Users\root\Desktop\New C\mult>gcc main65536.c -O3 -o main65536.exe

C:\Users\root\Desktop\New C\mult>main65536

Start.

Test conversion of base 10 string (num1) to base 65536 register.

Calculating base 65536 representation of 4,294,967,295.

Done.

It should be, 65535 * 65536^0 + 65535 * 65536^1.

reg[0][0] = 65535
reg[0][1] = 65535
reg[0][2] = 0


Time conversion of 5000 digit base 10 string (num2) into base 65536 register.

CPU time = 0.047 seconds

Time conversion of base 65536 register back into 5000 digit base 10 string (num3).

CPU time = 0.390 seconds

Check that num3 equals num2.

num3:

25998305698778882782694282216427520062325059925056858892956364318072249183875081
68442463096175264507182962040625952405271506061048605031872834827638275762132253
73858445634105522970396018248984984361543008819047090626470992519569266493011239
81385713161641125513067028830936811472923500257024862707991584798971140541617300
71234231202135809223242312655616315542948583438071887907514024590102337732384078
73247871862406989702271177063193217340225057994600159267813767262212104205783683
63025095177920225074834669646252545408427449351069515060097278605753619956900553
86795407681744802443535225584885995769092731030367772359645778787948035071575082
53503289863240458955982431760859690441697916187389932839106208311038104759463304
92038066942096086838928671505951410997562150419005828041119390620070926224749330
44811876158602334452145258026429850607093412457930099562830313117366885751915651
35310474958330215531787533896617511151902175564933090237349475682507288214834576
20981592706390501627359956921483881745921979876592412959264226532610844965533056
03823828082715947774513221424937375043663476412308396807105569420007984249340080
70124226805424103934896265174680289673701126520929835659871748979564184979293730
45550019576989200303483284173094578415208174108966111657697671143910071201004209
15169233837546621367856373302160998891694535450327805786016482732217698026063614
40603263939359332375698364136585280539910291370562457066811608026783236764726683
13253191452669007945741569955632534423125360266525673445710344893225336318036227
51899802490385922414156963217848785122664633235788479138790465438621496053154871
73265449103449852542128801432673156268199636851603649366783456131703429831019395
58616468939108822708875327843669816436591423630016096816579847927321181094384808
48971144589031804610332975513162952739089719888839081179410446068318437603084717
68065017203019228437269987546251968940949710370152901914623079970495510312155857
10531628560328469630530230738955807702048465618031979365349815954488779169464043
80983107076650841323914686794178090751465245823400769670464670326638076080844984
86090543541686857510467272349459625744971256146278089920197008015202026901138208
25817340003057701196678502919432716213170216770030043873909619982612504305878265
63384117053916125512691009340648815240201490510784486550498597569457045276884804
91865119934397485463815538073854196931715904770807149099466503028609184021441221
59089675228893305861570418194732610445826552339848389548697585828630934265012947
51819363488772591396849482145412316967315364801141150691652872346064364671557159
57870568873819933917795169659740301812765066254701635819988078720330945566076017
12466383911567471431945132028284492008888627473183080652614885161771855164380212
56512978748066431943525241224310973011888837173654921579048402850423671702268989
49476674471179823846251058464063708473349960106833310306786814275642736388131948
78853304014653428237678819866297610838549351485990743483386487071371788942431356
45129870888909362061936491534282424966231253781963484583313517427756831015160329
08460421876455141368075149317323870087337557877266063706878152841099564845544576
02584912275268492270010276806384202285220161843604109696931612250710695403166096
12011524876010688857641908772551802101359360026299544825344854352115301284299126
01871502787383611403333990220554059532815646775153885994405874220641555781568174
59134199947346374100959559692603359039655243341220363085112018667091742696030637
78755681701026350607067305932389961340795092328701602727982045965114355375309786
44330218738767773351405955056229902373326329657681337365859884155874806028591436
77242431693996079457476508502891472765537837945937191083770030828201762130870310
22795161096202928541405933619254574989906246644841265211804433276386092566107158
24199398366344967746652790939781016393178900620040351585430416904327025672216116
83434360955191759751176141733345322786732343897113347147010081549975643292804851
44171393681671875475203079259426309412509694297381930371443878319798964013436284
65780117439778511809284751185576752596740554256973137622081957317901735882634841
45264502282597981982093584294482163518729558095112079267612165583911076485738457
06812494083903873366071851446397049289636785999680657649308477853651523475322335
52576705584073135488835033287183224933798541691954594398983338870795422146462358
64356921050476220943937551133229566137714685998165093616730709543866077509213332
72538937423092381584439092507337482407136298806936136101125596769949786666162714
84145287731493057723165366990353272203559326978429596689051304429723917210971987
63646897153112540248997458505889304985958232516312646311735644831173300178649902
79267177572324356566298423592454528203459564599092014966942998266943638616048878
56263567748856093177664375222549588154447598478535276027080215208489307640259709
39579660389428258923069620672692556578816868263589345214720402757856535244008389
11635718199286310046144595079464600464592471156199566437490374949272866165344859
2183668353072789614088833332061767578125

Total time for conversion of 5000 digit base 10 string into base 65536 register,
and back into base 10 string.

CPU time = 0.452 seconds

All done. Press 'Enter'.

[kryton9]

I guess this thread answered my question I posted in the other thread about the Toom - Cook method.

Dan, I think you are working on a secret dark project in California building space ships that travel vast distances :)