Skip to content

TanmayPatil105/pow

Repository files navigation

This program implements an algorithm to calculate the value of 'A' raised to the power of 'B'. ie. A ^ B

No! This does not take less time than the original pow implemented in glibc. The original glibc implementation is almost twice as fast as this one.

But worth the time wasted.

Algorithm

Let's go step by step.
If you have taken a look at the code. you'll see a magic (mgk) array defined and it's calculation takes up most of the time. Here are the magic array's computed for different B values:

1 -> [ 1]
2 -> [ 1, 2]
3 -> [ 1, 6, 6]
4 -> [ 1, 14, 36, 24]
5 -> [ 1, 30, 150, 240, 120]
6 -> [ 1, 62, 540, 1560, 1800, 720]
7 -> [ 1, 126, 1806, 8400, 16800, 15120, 5040]

Let's dissect on what's happening here:

For this algorithm what is we use is recursive difference method.
In order to find this algorithm first I had to do some hardwork of calculating the power's beforehand using a calculator.
Let's say we want to calculate 3^4.

  1. How did we get to the magic array?

Power of 4

In the figure above, the blue column displays the numbers from 1 to N, while the purple column shows those numbers raised to the power of 4.
Now, to get to our magic array, we will perform recursive differences until we obtain a common difference.
So, if you look at the inclined grid, you'll notice the number present at a location is equal to the difference between the number in the previous column and the number above the number in the previous column.

To better understand here's a expression: grid[x][y] = grid[x-1][y] - grid[x-1][y-1].

This process continues until we obtain a common difference, which in the example above is 24. If you do some quick calculations, you'll realize that 4! = 24.

We can generalize this: while taking recursive differences of the nth power of numbers, we will reach a common difference equal to n!.

But where is the magic array?
The numbers marked in red, combined with the common difference, form our magic array.
In the case of 4, as we mentioned earlier, it is [1,14,36] + [24].

Let's create the same diagram for power of 3.

Power of 3

The importance of magic array is we can generate the whole grid above by using it. Take a look:

1 = 0 + 1
15 = 1 + 14
16 = 1 + 15
50 = 14 + 36
65 = 15 + 50
81 = 16 + 65

which is equal to 3^4. Similarly, we can calculate fourth power of all other numbers.

  1. How to generate this magic arrays?

Now the most important problem is how we can find these numbers in magic arrays. Do they share any patterns, and does this pattern work for all magic arrays? Yes!

Magic array's

Here, number present at every location is equal to the sum of number in the previous row and the number to the left to the number the previous row multiplied by the column number.

grid[x][y] = (grid[x][y-1] + grid[x-1][y-1]) * column.

Summary

  1. The first step is to generate the magic array.
  2. Next, create the inclined grid, and use the sum of its numbers to calculate the powers.

Tests

pow (2, 18000) = 3466745429523766868669875201719137528580444595048549101118260943266639857068382934568148647598693689476027886073289708998658484404112522762803277048875929624763619202277389565745632136627531638561811529302270317023945889677601070834646152283725860940678708218692055241033824279768703157515370800265271650620158955950890789222179414868679373682038581607582138035231803499300332215525586652834955220251131283536412267315428323787511236993556828237137351445763441215605062551563941542435689733918295856082539874553764061288332692528985765225895240123736960716733982091696821447186469572701037016067066655697327978743913822915903811541090663468906796336350680410722631021749004762071937153476277746518173322958225484034407034244899220136460577608531311312487181862234616933207818775725578764079189079180223379778490843975608207231679575715315931687222342284338676685773413493005811679860281408087852395865361850182265500625024374804191460864354854106851237688157847752664014656989256174088160718293609880169404298653163471076102851161248744625432274142076370401926474950118314403812441248508501110234926454814825062327166770975746266615608930894681737916044575489285351358860753580234435114925778796592057058591847194073255704845122667622300676232816383881663415933822759552992687544059146405098667498542640455210322463750363717121900062452302016759110698828640364482337131529115573344800916244658348894434368129959706489220610934894872375761383213638477006424544816467320068233207316031341530285868730381994796310243391722606841439542216481221814656683298619719569783832869243906214223659661661672301921261405213766417469708294728498591825562227028272962195867977797555184300880665673192270778320319397783661966865423833964650592906921187116100904108530419124385520033801247935442979349084958166960096381306582576591732388625229369225435281269798040285859325172648918283162991266001207936050803978230564451726132268717389266573447353270999630387278068681629236702878532651866937326547376306298759875213865728466209291452190518778368214689433923474900690743698014479740952347712759770436031047940285022105423904298440268980305945253267123089503210291805777368776438954628040032540436229221205155567034644354618019111524189486893593602933371966832243477848139399141884034499812297337000731453430598090876255578172355833825770949446738893252531709766798753631178635778829943193062914112399508840336217677194720000238609026531314058206822625990751464926198120177102127995522391956695113060029952847581449309398042189101278011415961850392519962162469897658479841901519632996960252306338917028592236254373926001549369577071945103259317223937084815844536524711639127838867446544975069463794304979084953771451928808710187997969713806074924255816313345752062085426231810198922436363114040542519697009174038916780003104721012999688173145257113904266587507573690365625931560679443914726977031959714121040926079681349349306451416977350469772215305379074953943060217477701480598285487862711820782704979643159629202795521017364198013997484900377451574775724058686846693297453967157892715267851097757693229944262513415542969631595833973527523841456620886817374561060679920918448779267147405919008602884815016875666121933539744336790745267160483113476523927550795108814985742155870454613889201865013990710544909767091957652642591016901277956674363964321575723491596970281419271028056528129783969637446999350932041128058924499394371786223210976336161848335065554709154934405172420989752718355742568992398071460932023039361448824275396734743650585868894656400651458867126833869947552418813520158564864569991537207632167039153491031179952791325779878058820574989893999981213967303477575024799961794896903097060745901172488812768071052971078257596533849096896963786097934781910675507229932359772343178317483463270886897398810823752912433387482556321274836357386530210277444960894291600558519930199677073212308322595636004830156377165284596407991620095174828908558667420712349061161688996902128380696743454917615993000901753063115968839803511161564408547621027764594609446216751492700261952161982828999900776636697692734924374830516579398631304897271666967529912147924439414725561283749408157519908936562787632633405850323272247739233425636923042453393320162433559390380667577308126639718422845730147964355078917273280024156364495091370199222940021018205371559723587482883796082885152094719511798379582214727689976266911542354078492013801934078616867821651189390395135352386785030500860198000641008918507822557434342724622515376649362661754588723602908665986188974683036160125444410573390773897420172754373932486563477307727729720901588946314641069922947960599784154540529415860517945726551866092288996571946292997554524404956482902108127925623263624656314999056476406341480861315827042045846327567723985927092168611444231317253652302766061592043158654928151496523030751707782642124364008446942216392199263833208513605154748746262935597866344481698065255702161291291528025816024003773741989731123299511076201131096241429620950849677082854717721864235196127706743170249384061545256091327156936706483579413026248777790629684044779249804993805600558408900028965035082396587528040728622309369868533357895550904419266675425004371924234589251343122697617593738786233924312055470267630128838789134854292446045985192331216793372318925438942555659227679298529525985550247011426983293707462778873808721405985472574230377291014132619196882394116444389376

________________________________________________________
Executed in   83.08 mins    fish           external
   usr time   82.92 mins    1.31 millis   82.92 mins
   sys time    0.12 mins    2.14 millis    0.12 mins

With/Without using OpenMP

# with
Executed in  447.67 secs    fish           external

# without
Executed in  666.89 secs    fish           external

About

No description, website, or topics provided.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages