C++

Forum

 
Big number arithmetic

gigis74 (1)
I've been looking on this code a lot and I even rewrote it and I still can't find what's wrong.It has to print the factorial of an entry n.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
 
  #include <bits/stdc++.h>
using namespace std;

int a[2600],b[30],c[2600];
int n;

void Produs(int a[],int b[],int c[])
{
    memset(c,0,sizeof(c));
    int i,j,t=0;
    c[0]=a[0]+b[0]-1;
    for(i=1;i<=a[0];++i)
        for(j=1;j<=b[0];++j)
            c[i+j-1]+=a[i]*b[j];
    for(i=1;i<=c[0];++i)
    {
        t+=c[i];
        c[i]=t%10;
        t/=10;
    }
    while(t) c[++c[0]]=t%10,t/=10;
    return;
}

int main()
{
    int i,j;
    cin>>n;
    for(i=1;i<=n;++i)
    {
        b[0]=0;
        int cpi=i;                                               /// formez numarul b
        while(cpi) b[++b[0]]=cpi%10,cpi/=10;

        Produs(a,b,c); /// calculez a* nr curent din factorial

        a[0]=c[0];
        for(j=1;j<=c[0];++j)            /// transfer din vectorul c in vectorul a pt a relua op.
            a[j]=c[j];
    }
    for(i=a[0];i>=1;--i)
        cout<<a[i];
    return 0;
}


/*#include <bits/stdc++.h>
using namespace std;

int a[2600],b[30],c[2600];
int n;

void Multiply(int a[],int b[],int c[])
{
    int i,j,t;
    memset(c,0,sizeof(c));
    c[0]=a[0]+b[0]-1;
    for(i=1;i<=a[0];++i)
        for(j=1;j<=b[0];++j)
                c[i+j-1]+=a[i]*b[j];
    t=0;
    for(i=1;i<=c[0];++i)
    {
        t+=c[i];
        c[i]=t%10;
        t/=10;
    }
    while(t) c[++c[0]]=t%10,t/=10;
    return;
}

int main()
{
    int i;
    cin>>n;
    for(i=1;i<=n;++i)
    {
        memset(b,0,sizeof(b));
        int icpy=i;
        while(icpy) b[++b[0]]=icpy%10,icpy/=10;
        Multiply(a,b,c);
        a[0]=c[0];
        for(int j=1;j<=c[0];++j) a[j]=c[j];
    }
    for(i=a[0];i>=1;--i)
        cout<<a[i];
    return 0;
}
*/
salem c (3700)
Some thoughts.

1. Don't use global variables when you're already passing parameters.

2. This doesn't do what you think it does -> memset(c,0,sizeof(c));
Arrays have no true size inside functions.

3. while(t) c[++c[0]]=t%10,t/=10;
This is an awful abuse of the comma operator to save a couple of characters for a ; and a couple of braces.

4. Produs(a,b,c); /// calculez a* nr curent din factorial
What did you initialise a to?
Enoizat (1343)
Could you please describe better what you are trying to achieve?
In order to calculate a factorial, perhaps a simple loop and a couple of ifs can do the trick.

If what you want is to go beyond the limits of primitive types, i.e. if long long is yet too little for you, then I think you need an external library like Boost::multiprecision:
https://www.boost.org/doc/libs/1_69_0/libs/multiprecision/doc/html/boost_multiprecision/intro.html

Otherwise, if you simply want to guarantee against overflow, perhaps you could try to forestall it:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
#include <iostream>
#include <limits>
#include <utility>


std::pair<long long, bool> calcFactorial(int val);


int main()
{
    std::cout << "Please input a number: ";
    int num;
    std::cin >> num;

    auto fact { calcFactorial(num) };
    if(fact.second) {
        std::cout << "The factorial of " << num << " is " << fact.first << '\n';
    } else {
        std::cout << "The highest factorial of " << num
                  << " I could calculate before overflow was " << fact.first
                  << '\n';
    }

    return 0;
}


std::pair<long long, bool> calcFactorial(int val)
{
    if ( val <  0 ) { return { 0ll, true }; }
    if ( val == 0 ) { return { 1ll, true }; }
    if ( val == 1 ) { return { 1ll, true }; }
    if ( val == 2 ) { return { 2ll, true }; }

    long long ret_val { 1 };
    for ( long long i { static_cast<long long>(val) }; 1 < i ; --i ) {
        if(std::numeric_limits<long long>::max() / i < ret_val ) {
            return { ret_val, false };
        }
        ret_val *= i;
    }

    return { ret_val, true };
}


Example output 1
Please input a number: 20
The factorial of 20 is 2432902008176640000

Example output 2
Please input a number: 21
The highest factorial of 21 I could calculate before overflow was 8515157028618240000

Perhaps I’m misunderstanding what you want to do. Please, add details.
dhayden (5798)
Please comment your code so we don't have to reverse engineer what you're trying to do and how you're storing your data.

In addition to what salem c said, you need to initialize a.

You might find it easier to write and read the code if you use functions to do some basic operations:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
#include <bits/stdc++.h>
using namespace std;

int a[2600], b[30], c[2600];
int n;

void
Produs(int a[], int b[], int c[])
{
    int i, j, t = 0;
    c[0] = a[0] + b[0] - 1;	// you'll have at least this many digits
    memset(c+1, 0, c[0]*sizeof(c[0]));
    for (i = 1; i <= a[0]; ++i)
	for (j = 1; j <= b[0]; ++j)
	    c[i + j - 1] += a[i] * b[j];
    // Add the carry for the digits you know you have
    for (i = 1; i <= c[0]; ++i) {
	t += c[i];
	c[i] = t % 10;
	t /= 10;
    }

    // Add additional carries into additional digits as needed
    while (t) {
	c[++c[0]] = t % 10;
	t /= 10;
    }
}

// Convert an unsigned to a big number
void unsignedToBig(unsigned u, int big[])
{
    int i = 1;
    do {
	big[i++] = u%10;
	u = u/10;
    } while (u);
    big[0] = i-1;
}

void writeBig(ostream &os, int big[])
{
    for (unsigned idx = big[0]; idx>0; --idx) {
	cout << big[idx];
    }
}

// Copy big number from src to dst
void bigcpy(int dst[], int src[])
{
    for (int i=0; i<=src[0]; ++i) {
	dst[i] = src[i];
    }
}

int
main()
{
    int i;
    cin >> n;
    unsignedToBig(1,a);
    for (i = 2; i <= n; ++i) {
	unsignedToBig(i,b);
	Produs(a, b, c);	 /// calculez a* nr curent din factorial
	bigcpy(a,c);
    }
    writeBig(cout, a);
    return 0;
}

Zivojin (132)
If you want to use big numbers you can create a class BigNumber where you would have a int * type variable so you would basically put numbers in one big array.
dhayden (5798)
If you want to use big numbers you can create a class BigNumber where you would have a int * type variable so you would basically put numbers in one big array.
It would be better to use a vector<int> since the number of digits varies. There are other cool tricks, like using a larger base such as 1000 or 10000, or a binary base like 256 or 1024. That makes the arithmetic faster at the expense of harder conversion to decimal for output.

If the goal is just to use large numbers, there are good classes available for free such as bignum.
Topic archived. No new replies allowed.