Finally I'm done! with my big num implementation.

wtf (670)
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
 
#include <stdio.h>
#include <stdexcept>
using namespace std;

runtime_error Negative_Factorial("Negative factorial not supported");

#define very long
#define big long
#define number int

bool clearbuf()
    {char ioch; do ;  while( (ioch = getchar() != '\n' ) ); return true;}
very big factorial(very big x);

int main()
{
    very big number n;
    bool b = true;
    while(b)
        {
            do{
                printf("Enter a number:\n>");
            }while(!scanf("%lld", &n) && clearbuf());
            try
                {
                    printf("%lld! = %lld.\n", n, factorial(n));
                }
            catch (runtime_error & rt_e)
                {
                    printf("%s\n", rt_e.what());
                }

            do{
                printf("Continue? 1 for Yes 0 for No\n>");
            }while( (!scanf("%d", &b) && clearbuf()) || (b!=0 && b!=1));
        }
    return 0;
}

very big factorial(very big x)
{
    if (x < 0)
        throw Negative_Factorial;
    if (x == 0 || x == 1)
        return 1;
    return x*factorial(x-1);
}


Before it was only computing accurate results up to about 13!.
Now ive tested it up to and including 16!, 17!, 18!, 19! and 20!.
No need to bother testing any other values because I'm sure its perfect right?
rapidcoder (1010)
Nice joke. :)
Null (957)
You only need to modify 2 lines of code to be able to calculate factorials up to 1754!, which is equal to
76231942073770349794838328651979841753193672001642307758818721255580718022006055
86624897037870168402192750354683901371167954338441233101412391016861928006819024
31686950621322344103684963506508299388268470178087741492245356860975267489366500
31885401571770372961507246206623513519435410551942570431588435406096750724479082
66747442694779693271275625905162991558428024797357498290175934608776530314835464
90347815115465759806072793439765142235640043176524836922757441009738583133174559
28538247510442106005321431401175229733644737802235660224185809074299857054494559
10418485579485336879492441449760389365912653485252372037909830963249405108104253
54877703445463980395858540125633951625874987185632201091431400205722926440010509
32465825847113879950667684799861426817832109594143864120294369449273474706971580
59534383975977724748342492255032676191199050046388732476133109881363960919967702
68389625140979016110737871799986275128205839628544876991392766612407598074855000
18356463362844489172217523665700099520624962204149712559210527539395965061104591
62890502135573562557037370393488209109096950347818817341853656944820163940157902
22587358200297532426541754616287945785873633438197508196888799418896702604659751
72532514623321890818078661652305912780276047551141481176204280556222657307754144
71278888693764470123466586820863416749147364220592619471177011768619205983179801
03398794650445491371606681383790067208225161213624619380909245134784433568537108
72052811062108095307454433763079005631166295742211183641386246726734934186113095
30426670898241804633051747554969124193251370002935050517852199813133883136379309
13975473686771052195166580162870997484374345038314109298724584523389931736813508
26214080250663425659092180929231353847683317703486586338078372746737292057135218
81489901252466190325984708138502065278557285405816157387741358011104554497688686
53806271468874265928992599660499643115383114814724754549588157141422669537326093
15305234910549481796254130284473056483963712434743652228374717724554056121725018
31105819480281660524752076445635674064111164484503817344876336982583660470890991
23066895188923839150788846571012840377178574352678383086698882113832924101165030
82104099343093188156773904640315293461224502322720033140734390029397043878878710
55310731736070014958552233350025195859006759041932363749060800654468613018772921
66458562210685914795872822916531005613557294727480319984481336670559962068493256
99579696246041789158873836443405987928827722722530561439667457569915503066319055
01669509891422091558878374974656837600873729798008290992519443998111738599637728
82535307634645183188402736946444764260698711096979971403128256162804128282604183
30667162136057507180969922753865789935084386009180986933568188934783047318504875
17981798906946781125517813589282895824917540881222651898777597160541422307305397
653419142087117334240920115573918239455805735698432.000000

wtf (670)
Any multiple of a multiple of 10 will end in zeros. Yours ends in 2.
Null (957)
why are floats so damn inaccurate?
wtf (670)
On a serious note:

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
 
#include "integer.h"
#include <stdexcept>

using namespace std;

runtime_error Negative_Factorial("Negative factorial not supported");

bool clearbuf()
    {char ioch; do ;  while( (ioch = getchar() != '\n' ) ); return true;}

integer factorial(integer x);

int main()
{
    integer x, y, z;
    very big number xnum;
    bool b = true;

    while(b)
        {
            x = 0; x.POS = true;
            do{
                printf("Enter a number:\n>");
            }while(!scanf("%lld", &xnum) && clearbuf());
            try
                {
                    very big number ceiling = (xnum < 0) ? xnum * -1:xnum;
                    for (integer i; i < ((xnum < 0) ? -1 * xnum:xnum); ++i, ++x);
                    if (xnum < 0) x.POS = false;
                    z = factorial(x);
                    printf("You typed: "); x.cout(); printf("\n");
                    printf("%lld! = ", xnum); z.cout();
                    printf("\n\n");
                }
            catch (runtime_error & rt_e)
                {
                    printf("%s\n", rt_e.what());
                }

            do{
                printf("Continue? 1 for Yes 0 for No\n>");
            }while( (!scanf("%d", &b) && clearbuf()) || (b!=0 && b!=1));
        }
}

integer factorial(integer x)
{
    if (x < 0)
        throw Negative_Factorial;
    if (x == (integer)0 || x == (integer)1)
        return 1;
    return x*factorial(x-1);
}


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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
 
#ifndef INTEGER_H
#define INTEGER_H

#include <string>

#define very long
#define big long
#define number int

very long get_int_size(very long n)
{//I think this is for positive ints only
    int tn = n;
    (n < 0) ? tn *=  -1 :1;
    very long counter = 0, divisor = 1;
    while( (++counter) && (divisor *= 10) )
        if ((tn/divisor) >= 1)
            continue;
        else break;
    return counter;
}

int nth_digit(int n, int d)
{
    int tn = n;
    if (tn<0)
        tn *= -1;  //do I need this?
    int s = get_int_size(tn);
    if (d > s || d < 1)
        return -1;
    int increment = 1,place_holder = 10, counter = 0;
    for (int i = 1; i < d; i++)
        {
            tn = tn - (increment * nth_digit(tn, i));
            place_holder *= 10;
            increment *=10;
        }
    do
        if (tn % place_holder == 0)
            return ((place_holder - (counter*increment)) %place_holder )/increment;
        while( ( (tn +=increment) && (++counter) ) && (tn <= (n + place_holder)) + 10 );
    return -2;
}


bool is_valid_string_for_integer(std::string s)
{
    if ( (s[0] != '-') && (!isdigit(s[0])))
        return false;
    int size = s.size(); int i = 1;
    while(size-1 > i++)
        if (!isdigit(s[i]))
            return false;
    return true;
}

class integer
{
    public:
    short * d;
    bool POS;
    public:
    integer()
    {d = new short[1]; d[0] = 0; size = 1; POS = true;}
    integer(const integer & a){POS = a.POS; d = new short[a.size]; size = a.size; for (int i = 0; i < size; ++i) d[i] = a.d[i];}
    integer(const very big &vln){POS = (vln >= 0) ? true:false; size = get_int_size(vln); d = new short[size]; for (very big number i = size-1; i >= 0; --i) d[i] = nth_digit(vln, size - i ); }
    ~integer(){delete [] d;  }
    int size;
    bool resize(very long ns);
    bool operator ++()
        {
            very big number x = size - 1;
            for (; x>=0; x--)
                if (d[x] < 9)
                    {d[x]++; return true;}
                else d[x] = 0;
            resize(size+1);
            //sv.d[0] = 1;
            d[0] = 1;
            for (very big number i(1); i < size; ++i)
                d[i] = 0;
            //std::cout << "sv.d[1] = " << sv.d[1] << ".\n";
            //*this = sv;
            return true;


            resize(size+1);
            d[0] = 1;
            for (int i = 1; i < size; ++i)
                d[i] = 0;
            return true;
            return false;
        }
    bool operator --()
        {
            if (POS)
                {
                    int i = size - 1;
                    for (i; i >= 0; --i)
                        {
                            if (d[i] >= 0)
                                {
                                    return --d[i];
                                }
                        }
                }

        }

    integer operator +(const integer & rhs)
        {
            integer copy(*this), r(rhs);
            for (integer i; i < rhs; ++i)
                ++copy;
            return copy;
        }
    integer operator - (const integer & rhs)
        {
            integer copy(*this);
            for (integer i; i < rhs; ++i)
                --copy;
            return copy;
        }
    bool operator <(const integer & rhs)
        {
            if (POS && !rhs.POS)
                return false;
            if (rhs.POS && !POS)
                return true;
            if (!POS && !rhs.POS)
                {
                    integer a(*this), b(rhs);
                    a.POS = true; b.POS = true;
                    return a > b;
                }
            if (size < rhs.size)
                return true;
            if (size > rhs.size)
                return false;
            if (*this == rhs)
                return false;
            for (int i = 0; i < size; ++i)
                {
                    if (d[i] > rhs.d[i])
                    return false;
                }
            return true;
        }

    bool operator >(const integer & rhs)
        {
            if (POS && rhs.POS)
                {
                    if (size > rhs.size)
                        return true;
                    if (size < rhs.size)
                        return false;
                    for (int i = 0; i < size; ++i)
                        if (d[i] != rhs.d[i])
                            if (rhs.d[i] > d[i])
                                return false;
                    return true;
                }
            if (POS && !rhs.POS)
                {
                    return true;
                }
            if (!POS && !rhs.POS)
                {
                    integer a(*this), b(rhs);
                    a.POS = true; b.POS = true;
                    return a < b;
                }
            if (!POS && rhs.POS)
                {
                    return false;
                }
        }
    integer operator *(const integer & rhs)
        {
            integer ov(*this), rv;
            rv.POS = true; ov.POS = true;
            for (integer i; i < rhs; ++i)
                rv += ov;
            rv.POS = (rhs.POS == POS) ? true:false;
            return rv;
        }
    bool operator +=(const integer & rhs)
    {
        integer temp(*this);
        temp = *this + rhs;
        if (temp == *this + rhs)
            {
                *this = temp;
                return true;
            }
        else return false;
    }

    bool operator == (const integer & rhs)
    {
        if (POS != rhs.POS)
            return false;
        if (rhs.size != size)
            return false;
        for (int i = 0; i < size; ++i)
            if (d[i] != rhs.d[i])
                return false;
        return true;
    }

    bool operator = (const integer & rhs)
    {
        integer temp(rhs);
        if (temp==rhs)
            {
                POS = temp.POS;
                size = temp.size;
                for (int i = 0; i < size; ++i)
                    d[i] = temp.d[i];
                return true;
            }
        else return false;
    }

    bool cout()
        {
            if (!POS)
                printf("-");
            for (int i = 0; i < size; ++i)
                printf("%d", d[i]);
        }
};

bool integer::resize(very long ns)
{
    integer copy(*this);
    size = ns;
    delete [] d;
    d = new short [size];
    for (int i = 0; i < size; ++i)
        d[i] = copy.d[i];
    return true;
}
#endif


computes accurate results all the way right up to 4!
closed account (D80DSL3A)
@Null
Further info re: 1754!. From a problem I found on http://www.codechef.com the # of terminating zeros in N! = the # of factors of 5 in N!.

For 1754! the Number of zeroes at the end = 1754/5 + 1754/25 + 1754/125 + 1754/625
= 350 + 70 + 14 + 2 = 436.
Expect the number to end in 436 zeros.

@wtf Hang in there, you'll get it!

Using my BigInt class (from the contest here last November) I get:

1754! = 197926189010501005538179432753260580461080687837386093244192650888193044
83104993781885087202818113141758217913524290130054389296110993761638740562668086
72031988042726293569869396758195522469778435225345119304425832697633115641694705
64381293304484848733495148291976456212394444854482391469358961537755901117325878
18296459849627459353506090190816436768622149143245877010092044525541198101437008
40085596837216739629073938640934217007950434342105036981626207737584801994362163
32263050292414532550118078744934714416138931668864042276417548741915510069523006
89238289694917634254857480292477598617118146209420015426832674824141333871406874
92549503983361352556223082387044506795688239104321264008843384476507522285400737
52184461117961678152221122043263518584863658013928250689774138379740195981844036
97290305095734456302825425424297490396089928965335730526812103146098573107702157
85427017719976782544274935020141394672500919505732689727529031599298955128321713
26253960083637041670738847732892994552925821000133187240439781154791897959712275
93949165652573800863631369880751519155681479325163622535064222024958212870621175
90439304317515743266031498005644908319537246536880185081266031343889190068372728
71560804998517093188544754285883618385586080775618565338425348556077656074480859
74124739026430012766042603940126063334294969408951800845891360188126920571835980
82952800726712622111807070601676933448560485743597927148074846682087776084514013
46857534159678514148349062240303985260422892648407181390646337957528447834208653
63989924190625578167655974198326049157940574049688969089004193589389716090830734
21813100896612913195792618987922512428211652825381178794237342656134741493186233
27743257075982668662589537128985055827525419542351810291196782068605371160089752
99892598378816005948758884516848732853390040677868297719380398400159684539103544
14949366151274275799723879125902342819697102639978601445770895578713003826274190
94854449340672863971524291953484926207930615692959994979550359738075202381503902
27542055961666116335567397505885860681595664464708759869790588566250910283055947
91530902301100662359942278721272019700361790639089677862444224899354853226981734
72984361274533434285935236982110144889616238316727216791254224224801622333143031
69941078370282017550763154939294448124735222025459248459192152338866622222094242
69338269690294001411029563900414423210293857162201951657985438627913097962152657
15681395941839373915035143753481131793443432264532519045167786895907114319237462
01292184718994258818836875617505592808566870904747986422748225938961565059060448
48894526213538331086947835069197391607650926018871984308002287761188793009453037
14466907164226974744141557228596979716771333021638771570077068808281835439416352
79586566948799583204081206405735205957552603718396907735093135159909966208491364
38513681745071916339778970844708854208079894782258096895939047561826015853788307
66632312270227224597154668574680444456093851166660808456131761713198785904486401
33042036507933133070095794241996956705966524579565419900183122902900392875206590
94819368329763452426235961930347693456681636738905842901924392198906203537992459
63194335157208533892660466688187505867684180955751465233492134765629957012978945
63555064586731292996256428087793552467410803796751623176328455748919329968098375
61460238705835057436850559167832652800067828559493836088361708886770178575730793
17064003495153239745887276674229901769274894755798456965869986871728696813409136
42717877619860889917131362661581527423608077008497788947393888299908446015746204
58730738571225971527271983647808337019595991393325237562979963158785560942386383
08799429665701123098730033480679715352336669595181870614059596863688896906374354
69783137327238909818780511672362538336877756625232796700675357521076858873186315
70152403076291967712200927642888075717987131118694140223747970641670962988969783
50766015356295011814776810463481044918665268867653365710135502271287557200054912
11081737694967647877807138342235204593794157730576529153242539457357788859841046
77457268794402025120637077087423324916255561298210485114795360663128922404919465
83248483980793565521994383850297294113334597747646224284552349466515610308646090
32738009475123065021416164689270243374366813187498401308112931643696460069958446
51059163191608133412757827063711410766016061992555235724530579404538249339332058
56309137210379916745291551115214127301185150657566662984843064875806617339169029
81429567350361526982783321369746306387727818096627121448147270649707938784751870
60974057976700004728832000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000

Can anyone check this?
Last edited on
helios (17607)
The value seems correct. I get a number that ends in "6700004728832" followed by many zeroes.
shacktar (1187)
Aside:

1754! has 4931 digits, so it is in the 1642nd -illion (where the 1st -illion is million, the 2nd -illion is billion, etc.)

Thus, 1754! is approx. 19.8 Duoquadragintasescentimillinillion

(I hope I've extrapolated correctly)

http://en.wikipedia.org/wiki/Names_of_large_numbers
Last edited on
Topic archived. No new replies allowed.