0

I have seen many answers here and on the internet but i don't need a big int library, I need a program that multiplies big numbers in c++/c but really fast, I have tried different prorgams and some of them are not runing really fast, so please help me with this multiplication problem, thanks.

Here is what i have tried, it is good, but not very fast. It works, but not for numbers that have 1000 digits, please help me:

#include<iostream>
#include<fstream>
#include<string.h>
#define MAX 300000
using namespace std;
ifstream fin("test.in");
ofstream fout("test.out");
void reverse(char *from, char *to ){
    int len=strlen(from);
    int l;
    for(l=0;l<len;l++)to[l]=from[len-l-1];
    to[len]='\0';
}
void mult(char *first,char *sec,char *result){
    char F[MAX],S[MAX],temp[MAX];
    int f_len,s_len,f,s,r,t_len,hold,res;
    f_len=strlen(first);
    s_len=strlen(sec);
    reverse(first,F);
    reverse(sec,S);
    t_len=f_len+s_len;
    r=-1;
    for(f=0;f<=t_len;f++)temp[f]='0';
    temp[f]='\0';
    for(s=0;s<s_len;s++){
        hold=0;
        for(f=0;f<f_len;f++){
            res=(F[f]-'0')*(S[s]-'0')+hold+(temp[f+s]-'0');
            temp[f+s]=res%10+'0';
            hold=res/10;
            if(f+s>r)r=f+s;
        }
        while(hold!=0){
            res=hold+temp[f+s]-'0';
            hold=res/10;
            temp[f+s]=res%10+'0';
            if(r<f+s)r=f+s;
            f++;
        }
    }
    for(;r>0 && temp[r]=='0';r--);
    temp[r+1]='\0';
    reverse(temp,result);
}
int main(){
    char fir[MAX],sec[MAX],res[MAX];
    int m,n;
    fin>>m>>fir;
    n=strlen(fir);
    for(int i=0;i<n;i++)sec[i]=fir[i];
    for(int i=1;i<m;i++)
    {
      mult(fir,sec,res);
      int len=strlen(res);
      if(i<m-1)
      for(int j=0;j<len;j++)fir[j]=res[j];
      else for(int j=0;j<len;j++)fout<<res[j];
    }
    return 0;
}
Ihor Dobrovolskyi
  • 1,241
  • 9
  • 19
Victor
  • 1
  • 3
  • Welcome to Stack Overflow. Please take the time to read [The Tour](http://stackoverflow.com/tour) and refer to the material from the [Help Center](http://stackoverflow.com/help/asking) what and how you can ask here. – πάντα ῥεῖ Dec 27 '16 at 15:34
  • 3
    This question seems to be better suited at [SE CodeReview](http://codereview.stackexchange.com/). – πάντα ῥεῖ Dec 27 '16 at 15:35
  • 5
    Sounds to me like a bigint library such as [GMP](https://gmplib.org/) *is* what you need. – dbush Dec 27 '16 at 15:38
  • You have a lot of subtracting/adding '0'. You may get a benefit from taking that out of your inner loops. Subtract '0' from all your digits at the beginning and add '0' to all the digits at the very end. – Vaughn Cato Dec 27 '16 at 15:39
  • You say you don't need a bigint library because they are "too slow", but here you go rolling your own which you say is also too slow. Yes, they'll be slower in principle than regular ints because they exceed the precision of your processor. That's just reality. So what benchmarks are you using to decide what is fast enough? Are those reasonable benchmarks? – metal Dec 27 '16 at 15:46
  • Also, you should give more deliberate consideration to one of the libraries already existing, unless this is homework to implement your own. [Boost.Multiprecision](http://www.boost.org/doc/libs/1_63_0/libs/multiprecision/doc/html/boost_multiprecision/intro.html), for instance, is a high quality library that supports multiple backends such as GMP and MPFR. The authors of this library have likely put more thought into performance and correctness than you have so far. Why not leverage their skill? Slow and working (theirs, allegedly) is better than slow and not working (yours, as stated). – metal Dec 27 '16 at 15:48
  • No, bigint libraries are not slow, but i can't use them in an olympiad – Victor Dec 27 '16 at 15:48
  • in the national olympiad of informatics i can't use a big int library, and i have tried to impliment it but it doesn't work, and still i don't need it, i want something like my algorithm but faster, maybe in less lines of code, if somebody can help – Victor Dec 27 '16 at 15:49
  • IOW, you want us to do your homework for you? – metal Dec 27 '16 at 15:50
  • It's not hoemwork, it is just for me so thta i would know how to use it – Victor Dec 27 '16 at 15:51
  • i ma learning this for my own benefit – Victor Dec 27 '16 at 15:52
  • Please refrain asking questions about online code judge engines here. It's very unlikely that anyone could tell you where you failed from their test cases, as these aren't disclosed usually. Even if what you tested was running at your local environment, you may have missed to test some edge cases which are applied in the online challenge. Be creative and try to find them. Additionally there's probably no value for such questions in the long term, other than cheating the online contest, and nothing is learned. – πάντα ῥεῖ Dec 27 '16 at 15:58
  • 2
    [karatsuba algorithm](https://en.wikipedia.org/wiki/Karatsuba_algorithm#Basic_step). – Adrian Colomitchi Dec 27 '16 at 16:02
  • see related QA with my C++ quest for: [Fast bignum square computation](http://stackoverflow.com/q/18465326/2521214) which covers also your question. The main idea is to use the correct multiplication algorithm based on operands size (thresholds). I would start with naive `O(n^2)` approach + Karatsuba. The NTT stuff is too advanced for beginners. Also usually the speed problem is due to poorly implemented recursion (stack/heap trashing) – Spektre Dec 29 '16 at 09:25
  • thank you very much – Victor Jan 01 '17 at 12:32

1 Answers1

0

The Toom-Cook algorithm is probably the better option for 1000-digit numbers. It works by dividing the input numbers into limbs of smaller size and reducing from 9 multiplications to 5; running in about Θ(n^1.465).

I am not well enough versed in C++/C to code this algorithm. If I were I would still not recommend writing it from scratch: Check out this code for Toom-Cook 3-way multiplication licensed (GPL 2.0) by Marco Bodrato and Paul Zimmerman.

John
  • 1
  • 2