The below code uses long multiplication code from the sub page C Programs/Long Multiplication. The idea is very simple if we want to find 2^1000 or say 2^10000, obviously the result will have large number of digits (302 and 3011 digits).
The code below is basically developed to handle this kind of problem.
Steps: The function int *power_of_xn(int a,int x,int *digitcount); loops through the long multiplication code.
For example: 2^10000 =
19950631168807583848837421626835850838234968318861924548520089498529438830221946631919961684036194597899331129423209124271556491349413781117593785932096323957855730046793794526765246551266059895520550086918193311542508608460618104685509074866089624888090489894838009253941633257850621568309473902556912388065225096643874441046759871626985453222868538161694315775629640762836880760732228535091641476183956381458969463899410840960536267821064621427333394036525565649530603142680234969400335934316651459297773279665775606172582031407994198179607378245683762280037302885487251900834464581454650557929601414833921615734588139257095379769119277800826957735674444123062018757836325502728323789270710373802866393031428133241401624195671690574061419654342324638801248856147305207431992259611796250130992860241708340807605932320161268492288496255841312844061536738951487114256315111089745514203313820202931640957596464756010405845841566072044962867016515061920631004186422275908670900574606417856951911456055068251250406007519842261898059237118054444788072906395242548339221982707404473162376760846613033778706039803413197133493654622700563169937455508241780972810983291314403571877524768509857276937926433221599399876886660808368837838027643282775172273657572744784112294389733810861607423253291974813120197604178281965697475898164531258434135959862784130128185406283476649088690521047580882615823961985770122407044330583075869039319604603404973156583208672105913300903752823415539745394397715257455290510212310947321610753474825740775273986348298498340756937955646638621874569499279016572103701364433135817214311791398222983845847334440270964182851005072927748364550578634501100852987812389473928699540834346158807043959118985815145779177143619698728131459483783202081474982171858011389071228250905826817436220577475921417653715687725614904582904992461028630081535583308130101987675856234343538955409175623400844887526162643568648833519463720377293240094456246923254350400678027273837755376406726898636241037491410966718557050759098100246789880178271925953381282421954028302759408448955014676668389697996886241636313376393903373455801407636741877711055384225739499110186468219696581651485130494222369947714763069155468217682876200362777257723781365331611196811280792669481887201298643660768551639860534602297871557517947385246369446923087894265948217008051120322365496288169035739121368338393591756418733850510970271613915439590991598154654417336311656936031122249937969999226781732358023111862644575299135758175008199839236284615249881088960232244362173771618086357015468484058622329792853875623486556440536962622018963571028812361567512543338303270029097668650568557157505516727518899194129711337690149916181315171544007728650573189557450920330185304847113818315407324053319038462084036421763703911550639789000742853672196280903477974533320468368795868580237952218629120080742819551317948157624448298518461509704888027274721574688131594750409732115080498190455803416826949787141316063210686391511681774304792596709376
Digits sum = 13561
Number of digits = 3011
#include <stdio.h>#include <stdlib.h>#include <math.h>/*2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.What is the sum of the digits of the number 2^1000?*/// 2^20 = 1 048 576// 2^100 = 1 267 650 600 228 229 401 496 703 205 376int *number_to_digit(int *n, int *digit_count);int *power_of_xn(int a,int x,int *digitcount);int split_lastDigit(int the_num,int *carryover);int *long_multiplication(int *multiplicant,int multiplicant_dgcount,int *multiplier,int multiplier_dgcount,int *product_dgcount);int *add_to_list(int *the_list,int the_value,int *list_count);int *long_addition(int *addition_dgtslist[],int addition_dgtscount[],int list_count, int *rslt_dgtcount);int main(){ int i,rsltdgcount; int *results = power_of_xn(2,10000,&rsltdgcount); int digits_sum = 0; for(i=(rsltdgcount-1);i>=0;i--) { digits_sum = digits_sum + (*(results+i)); printf("%d",*(results+i)); } printf("\n\n"); printf("Digits sum = %d\nNumber of digits = %d",digits_sum,rsltdgcount); return 0;}int *power_of_xn(int x,int n,int *digitcount){ // Returns the digits of pow(a,x) int i; int multicant_dgcount; int *result_digits = number_to_digit(&x,&multicant_dgcount);// for 1024 it stores as 4 2 0 1 and digitcount = 4 int multiplier_dgcount; int *multi_digits = number_to_digit(&x,&multiplier_dgcount);// for 1024 it stores as 4 2 0 1 and multiplier_dgcount = 4 for(i=1;i<n;i++) { result_digits = long_multiplication(result_digits,multicant_dgcount,multi_digits,multiplier_dgcount,digitcount); multicant_dgcount = (*digitcount); } return result_digits;}int *long_addition(int *addition_dgtslist[],int addition_dgtscount[],int list_count, int *rslt_dgtcount){ int i,j; // Find the maximum number of digits list // Idea is to fill zeroes for shorter numbers (numbers with less digits) int max_list_count = 0; for(i=0;i<list_count;i++) { if(max_list_count<addition_dgtscount[i]) { max_list_count = addition_dgtscount[i]; } } // Fill zeroes for shorter numbers for(i=0;i<list_count;i++) { for(j=addition_dgtscount[i];j<max_list_count;j++) { addition_dgtslist[i]=add_to_list(addition_dgtslist[i],0, &addition_dgtscount[i]); } } int *addition_result; (*rslt_dgtcount)=0; int carry_over = 0; int total_sum; for(j=0; j<max_list_count ;j++) { total_sum = carry_over; for(i=0;i<(list_count);i++) { total_sum = total_sum + (*(*(addition_dgtslist+i)+j)) ; //printf("%d",*(*(addition_dgtslist+i)+j)); } addition_result=add_to_list(addition_result,split_lastDigit(total_sum,&carry_over),rslt_dgtcount); } // To add carry Over digits to the list int temp_carryover = carry_over; if(carry_over!=0) { addition_result=add_to_list(addition_result,split_lastDigit(temp_carryover,&carry_over),rslt_dgtcount); temp_carryover = carry_over; }return addition_result;}int *long_multiplication(int *multiplicant,int multiplicant_dgcount,int *multiplier,int multiplier_dgcount,int *product_dgcount){ int i,j; //Loop variables int *product_summ[multiplier_dgcount]; //Variable to hold the digits of each multiplication results level int product_summ_dgcount[multiplier_dgcount]; for(i=0;i<multiplier_dgcount;i++) //Loop thro' all the digits of multiplier 9 4 for 49 { product_summ_dgcount[i] = 0; // set the product digit count as zero // Add zeroes at the end for(j=0;j<i;j++)// Have to add zeroes at the end of the product sum { product_summ[i]=add_to_list(product_summ[i],0,&product_summ_dgcount[i]);// added zeroes at the end } int carry_over = 0; //set the carryover as zero int temp_product; // variable to store temporary product for(j=0;j<multiplicant_dgcount;j++) //Loop thro' all the digits of multiplicant 4 2 0 1 for 1024 { temp_product = carry_over + ((*(multiplier+i))*(*(multiplicant+j))); product_summ[i]=add_to_list(product_summ[i],split_lastDigit(temp_product,&carry_over),&product_summ_dgcount[i]);// added the digit } //Add the carry over digits to the product_summ int carry_over_sum; int *carry_over_digits = number_to_digit(&carry_over,&carry_over_sum); //Split the carry_over digits for(j=0;j<carry_over_sum;j++) { product_summ[i]=add_to_list(product_summ[i],(*(carry_over_digits+j)),&product_summ_dgcount[i]);// added the carry over digits } } // Long addition (*product_dgcount)=0;// Set product digit count as zero int *result_product = long_addition(product_summ, product_summ_dgcount,multiplier_dgcount,product_dgcount); return result_product;}int *add_to_list(int *the_list,int the_value,int *list_count){ if((*list_count)==0)// There is no item in the list { the_list = (int *)malloc(1*sizeof(int)); // We initialize 1 space to the list } else { int *temp = (int *)realloc(the_list,(*(list_count)+1)*sizeof(int)); // Allocate one extra space if(temp != NULL) { the_list = temp; } else { printf("Error Allocating Memory"); } } *(the_list+(*(list_count))) = the_value; // Adding the value here *(list_count) =(*(list_count))+1; // Increment the list count after addition return the_list; // return the list address}int split_lastDigit(int the_num,int *carryover){ *(carryover) = (int)(the_num/10); return (the_num - (*(carryover)*10));}int *number_to_digit(int *n, int *digit_count){ int numP,numC = *(n); int *digits = (int *)malloc(1*sizeof(int)); //Initially we allocate 1 space to digit list *(digit_count) = 0;// set digit_count = 0 while(numC!=0) { numP = numC; //Set the numP value as numC then remove the last digit of numC //numC = numC/10 numC=floor(numC/10); *(digits+(*(digit_count))) =(int)(numP - (numC*10)); // (*(digit_count))=(*(digit_count))+1;//Update the digit count int *temp=(int *)realloc(digits,(*(digit_count)+1)*sizeof(int)); // give the pointer some (+1 int) memory each time if (temp != NULL ) { digits=temp; //Memory added here } else { printf("Error Allocating Memory"); } } return digits;// return the digits address and the digit_count is already updated}Another result,
The value of 2404^1299 =
682131125236916511484223025335331504656321496251690481401597127617646119216436194233251470753674664605965991367896714444410410109213362192912714640183368936867631848351877043226743390149533874425624500436515372462908029200753359015809689806060745304457053419097989886756725923767391174389053663644746945907533405860510564317984367401549679890548848813077195658592917556762077972260176293325950140000918499653977549312600631112013795931252270994418751445113608364551903059704086751816734791495842014970404605293400035605206937359888163251617496362663079425275943241650089239074436473834798493211086402251836057419266238441038507981701162856554554844561765969272392895840818962613300119352898119861675562631420108852340335396962817204272515988399912253891689846296952592457745164001226171957030120228061823174598395658644423291051812877947865910422897909148343396378591612584236628336493315953527361356792107047884074299179511025530997442093014993904890559582255686697041070543236554534171594169536588927822899327987931563645582854735324447563391412219024350789731675044943048397236060517218886481539053031063834709648033117490053494776962243165129751684445571375110446516705370809931257822061504469046979705550046650946696052894835903617072603871099460834618225636901640005527135778231562328741840948328566531009336441962400679753174312083167633452911335374867608905277753753477931369387689401482500510850223823832845456950830036632579697058873551390498673835039204011774683128691186193457681726982392400506395721994556834502096827700945600114988227914008453067996428086804388435993046169928220458020947893205299664761251116377016845445365398273729846357187961774030986063496062760994025887264715548004815199725813657227935370683405593767282453466643786723949255166971305147745039371682716059583413424553996903637558740260842625671231063847617435107298969889241465285224391778821369355564357839314096683475302985703807035830285408328622740433280296130175490710563017678573677068081544641167569989160960570745675663333302754525119896746279527806481715811169033649765773649511560228611982855361099364946333157531576861916906504860193604930145347546373303988968974496611910998460646578050295175149519577522808581923253172903609901891713174623157219489192840485646251998434266795420556028347844405658230992347005052481711874844205684402182312311939030658765189280094257062233533971556732132414052031526858195759796289708920763250067129845705243884765611025669899711738594171499707013240052259998569367857654534058022637433473690004380013664994409884137292494513300682210889973096759176822372238948988060657030356156088873615639389082626101185733093722807886454250207085302712536371287264057809226942419619794377482431222843846083292506143562507090600352056733269988713370536415540000733000320943979828398086757799026905354957058887307267136346093551812005711058594409429344740048847270920782482240926112857214008895385139165096160716377110370925418415296284287976007916678830412795120687770290624156969423686369677736816475141479827886519498919579307357711616903696323607023440518542605591863164659855052613390859316521487921977413680096087315331576477552837056161210246905780749789445398531838110337233696814167072672309842718482569296341471891015788269711701240828383226547557849986557262269420439515347302764505257263702264338850904770276453278285582995554084623043371617729625500933456365867132154186415771250862106825672635924671023414761831390954616836808720537773094284473616903976947017567912150743688966990788569009356996363063884028869918434379669398834577106802438999694740595090811997994530953935000412944350828581274580879671383711817474347972879810319573865391092530236022757509930139078856500338992570908051456621639450286836221452119544307648493530865560477905356936992054548836354630469705340860413224277012110364970821036092027573676424021034861026227936292396049288506238218317910631244885020642103137229590125376419142901548086231607129318950919006272035807657805208499828531832923256736508633179931164198848822875672456518744980300302432725854004791125495130342396949077926456360856559251733344952966224507050263190569632624424538129864689545267446257899179415662057840156364125012111314308269567299894086755583085412789478079843394478367377264312298374933051148035959470842783685395147681951622145640293874382327815362449042654217544214374204568329677315290648020527500754944
Digits sum = 19747
Number of digits = 4392