Thread: project euler problems

You need a "bignum" library, such as
GNU Multiple Precision Arithmetic Library - Wikipedia

@Salem 's right of course, and GMP is among the best, but don't overlook MPIR (a fork of GMP) if you're using MSVC.

If, instead, you're more interested in how that kind of thing is done (and it can get quite involved), if limited to the integer domain we could say that for a 32 bit machine to handle, say, 128 bit integers, you'd first think of the 32 bit "atomic sized" value (4 bytes) as one digit of a base (2^32) number. The 128 bit integer would be 4 of them, analogous to a 4 digit base 10 number (but instead of digits just 10 digits in one place, there are a little over 4 billion digits in each place). The rest basically operates similar to the grade school method of adding 3 and 4 digit numbers. Of course, then comes the evaluation (printing the output as a base 10 value to a string/stream).

For a 64 bit machine, naturally, it would be like a base of (2^64).

Lest you think this is unusual, and it is in the 21st century, back in the day it was the only way.

In '78 I had a 6502 based machine. The registers were 8 bits, and the CPU can't multiply (that had to be done as an algorithm, there was no 'mul' instruction in the CPU).

Just to handle 16 bit math required we put two bytes together and operate as if that was a base 255 (2^8) number.

Even in the first IBM PC, the CPU had 16 bit registers, but it did have the ability to provide a 32 bit result by placing the answer into two separate registers (which also happens on the modern CPU with two 64 bit numbers giving a potential 128 bit result from a standard math instruction).

Just an example, from the previous post, using GMP:

Code:

/* lcm-gmp.c */
/*
  Compile with:
 
    gcc -O2 -o lcm lcm.c -lgmp

  Install libgmp-dev package first.
*/
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <gmp.h>
 
int main( void )
{
  int32_t max, i;
  mpz_t n, m;
 
  /* Read from redirection (or keyboard) */
  if ( scanf( "%" SCNi32, &max ) != 1 )
  {
    fputs( "\033[31;1mError\033[m: Cannot read upper limit.\n", stderr );
    return EXIT_FAILURE;
  }
 
  // MAX can be as bit as 2^31 - 1!
  if ( max < 2 )
  {
    fputs( "\033[31;1mError\033[m: Upper limit must be greater than 1.\n", stderr );
    return EXIT_FAILURE;
  }
 
  mpz_init_set_ui( n, 2 );
 
  for ( i = 3; i <= max; i++ )
  {
    mpz_init( m );
    mpz_lcm_ui( m, n, i );   // libgmp has an LCM function already.
    mpz_set( n, m );
    mpz_clear( m );
  }
 
  // Show the result.
  mpz_out_str( stdout, 10, n );

  mpz_clear( n );

  printf( " is lcm of the range [1..%" PRIi32"].\n", max );

  
  return EXIT_SUCCESS;
}

Compiling, linking and running:

$ cc -O2 -o lcm-gmp lcm-gmp.c -lgmp
$ ./lcm-gmp <<< 10000
579333967028764296869227087916624009863486029799
851882539313835114897930014577318230883259817618
292216657441767940234070565594914024678915773283
267630212994668431184746378526568319385215494723
479710730681616793017054726852369264633873384952
205710644202506773150005994579413408494962272276
289264937710182648218422303703496401025734928814
243173061895694671014958346019912700399187809245
064954057979237622053607906520731593333827956704
260410335666993424490503097866736816704833691556
895675542398988790397441473339719882580610420909
704767292934845130724436147957668787263257958548
553944912908211671483555147491496837075852833815
461537030142104424703181805119066911083251464942
193434988993829180182465866098276674703291660121
108749811048004157415275862800267378481826736356
458722309052345151696111210428670439567278393141
987286262740666554678461833435991947615903686084
725783981697401114859240469868707148838942858413
949646274080941610192306627491012307830086686769
072111994881075233064105317720454528539577068732
384668299886498221575571035032835633982817754649
119047891595159009874015746788859424939076047408
918789076986226795709655694836824560429182364447
197945344111719076063360905340293493513002761418
925297954487518263943991532161832703857377957487
705086120963747653335782379733959072654843375029
039019477996633883298491980457562079695900556866
076781952063672736006329094170242247547504287112
369179136634192159258309440355398487491631784896
142275466560907901641081957410480336143684958272
312813921900630513152480701922634008013150956085
121395107314697323113138989957460405634331214277
760714826559043465382810106684767311324158298449
846004141367814047742135395078597902292058902717
216003091699268061218717500081637387739116100095
086091496653325796327673970788779969265813374193
518347543704110086861368185010308623455053853571
980608944638213422987178515678365629843448064696
137680247649673729796551790660743981982468051045
761344748230164888428180770416616760983993788097
138942849948653706486168006892255954319671810728
653634300052508407678909121645307057049368379155
848566069606873473723913392544321190859321755413
929543436847166951626292712297892894047521042185
969770369419105212663217268219405339863842379944
037806183013790993479752601227241944542750888255
870444882089656903737069040569265093246963088109
743317901194564381471685855520119269219121674505
099416461040768187620608819039696164316463849858
959442312185056205470938742411697592054501454787
461127968986267119663209650572122199585673388513
566317399471250962504529424974733092999076123304
351974543927886373592531163086850070142496054926
595244291345133441375171018722794282022859516528
563548272307659315028053416964701486980027377008
230789046345547767501691782592162559039688655887
498277898889501724524554482488337123098356575613
692331579774055793652936719431314120341099019448
928192450016574966718225812741805962553405070544
999340602823204582407224542099335697359400328591
099346868782741108643949244635738520153384288819
618432920835660346698146196126066382836157665218
975045666162723052539319383728304460733840192993
553208643427340195176336623467904229159519548226
451370914941261003901045109873733663286153630560
421374408082259736008095668457180737916169277842
605578450218230949993269043735923194075166608967
643880922625103691821535592854460749909418635162
472265326531421985518400636319894287767995332862
154646606441294115032873068385513411847399768070
977631153680317486460437805490551434282972306780
537384530102349490082537693552072081679992033531
575246660170298036796121318247407946525928756628
184799801175057685411948355242318182035522564267
527304551157522808370997632376063481928679364579
939708664462640158128191799941386422951088723817
091819370922903925443354640253246612847460036602
471611966982090621646372641149307664444734710834
082003296620590642018967211650156874877283008545
017808101558448374897981443099429990917744664062
700653054618482423293806362747546605198673431122
758618212935011121014348682253780418138368087454
176062891599042941659414086929222506011278049719
623428079277433900303950482632756169351653476207
180011574780884564390835908344644096227816937908
832895970240439825842200692241702358634587453443
656840821144303628674461936010755698036507730180
267000038122984605279762191003080165375380085977
515656315827456431394345083325155696454267719324
83266712323523039014220800000 is lcm of the range [1..10000].

Project Euler, problem 12's answer is an 8 digit number -> A 32bit integer is fine.


There is one question that I remember doing that had a massive number (I can't remember which one*) - To do that I created an array with element 0 being the LSB (little endian), and '-1' to indicate the upper limit of a number (like using a NUL character at the end of a string)

[edit] *Question 13 [/edit]

i.e.
For the number 9876543210 I would have

Code:

BigNumber[0] = 0 
BigNumber[1] = 1
BigNumber[2] = 2
BigNumber[3] = 3
BigNumber[4] = 4
BigNumber[5] = 5
BigNumber[6] = 6
BigNumber[7] = 7
BigNumber[8] = 8
BigNumber[9] = 9
BigNumber[10] = -1
...

Adding 2 numbers together is really easy to do with a "for" loop (which was all I had to do).


That being said, it is great experience using 3rd party libraries.

Originally Posted by cooper1200

i must be misunderstanding q 12 then as with the project the other day that asked what was the smallest number dividable by all the numbers 1 to 20 we proved that the limit of smallest number devisable by all the numbers 1 to 43 that was using a long long unsigned int

Edit: Divisors maybe counted differently the divisors of 8 are 2,2, and 2 for a count of 3. I am guessing this is the way they are counting the divisors.

Edit: I was wrong.

Code:

28: 1,2,4,7,14,28

6

Prime factor would have given 2,2,7 which is only three.

Tim S.

Originally Posted by stahta01

Edit: Divisors maybe counted differently the divisors of 8 are 2,2, and 2 for a count of 3. I am guessing this is the way they are counting the divisors.

Edit: I was wrong.

Code:

28: 1,2,4,7,14,28

6

Prime factor would have given 2,2,7 which is only three.

Tim S.

How to Find How Many Factors Are in a Number: 4 Steps


I don't know if you are already doing this, but it pays to do a bit of research on a topic before starting.

I always try to
1) Read up to understand the problem and what it is asking - You can burn a lot of time working on something that has nothing to do with the problem.
2) Research different algorithms and try to understand why they work - You can also go back to things you have done that have worked well in the past. (A good example is using a sieve of eratosthenes for anything prime related).
3) Create a version of the programme that can solve the example case (either given, or something that I have came up with). Can any data be put in a text file? Does it come in a text file? What would be the best way to work through the numbers (linked list, array, stack, anything else...)?
4) Try the programme with "full scale" inputs.


The first few questions you can fly through, but as they go on you'll need to get more of a research phase before any development. I'd imagine that you are now familiar with a development process (A development process). This is why I like Project Euler so much - It is actually getting you "job ready".

More on the job readiness - I've used printed out solutions for some Project Euler questions in job interviews. They are great because I could talk my way through the development process and I didn't have to worry about any IP problems with my current/past jobs.