Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › High-precision program that calculates 2^n
New Posts  All Forums:Forum Nav:

High-precision program that calculates 2^n

post #1 of 14
Thread Starter 
Hey guys, I'm building a program in C that can get powers of 2. The user inputs the value of n, and the program calculates 2^n.

Here's the code
Code:
#include <stdio.h>

double power(int n)
{
      int q;
      double c=2;
      for (q=n; q>1; q--) {c=2*c;}
      return c;
}

int main()
{
    int n;
    double output;
    scanf("%i",&n);
    output=power(n);
    printf("%.0lf",output);
    return 0;
}

The problem comes when I input 100
Quote:
What I am getting 1,267,650,600,228,229,400,000,000,000,000
What I should get 1,267,650,600,228,229,401,496,703,205,376

I've tried to modify the program, but so far, no luck...

It has to be coded entirely in ANSI C. Any ideas on how to increase the precision? The maximum value of N has to be 256 (256 bits, I imagine).

EDIT: I edited the code, look at it
Code:
#include <stdio.h>

long long power(int n)
{
      int q;
      long long c=2;
      for (q=n; q>1; q--) {c=2*c;}
      return c;
}

int main()
{
    int n;
    long long output;
    scanf("%i",&n);
    output=power(n);
    printf("%lld",output);
    return 0;
}

The problem is that, when I insert 63, it shows a negative number, and when inserting 64 and beyond, it prints 0.
Edited by Icekilla - 10/31/12 at 6:46pm
post #2 of 14
The problem lies in the max limit the data types you are using can hold. Long long can hold up to a bit past 9E18. While unsigned long long can hold up to 18E18. Therefore there is no way you could do something like 2^100. I would try to look for an external library which can hold bigger numbers.
First Build
(17 items)
 
  
CPUMotherboardGraphicsRAM
i7-2600k @4.5Ghz Gigabyte Z68X-UD7 B3 MSI 6950 G.Skill Sniper 2x4GB 
Hard DriveHard DriveHard DriveCooling
Crucial M4 64GB Samsung SpinPoint 250GB Hitachi 1TB Noctua NH-D14 
OSMonitorMonitorKeyboard
Windows Server 2012 Samsung S22B300 22' ViewSonic VA703B 17" CM Quickfire TK 
PowerCaseMouse
Corsair HX850 NZXT Phantom Mionix Naos 3200 
  hide details  
Reply
First Build
(17 items)
 
  
CPUMotherboardGraphicsRAM
i7-2600k @4.5Ghz Gigabyte Z68X-UD7 B3 MSI 6950 G.Skill Sniper 2x4GB 
Hard DriveHard DriveHard DriveCooling
Crucial M4 64GB Samsung SpinPoint 250GB Hitachi 1TB Noctua NH-D14 
OSMonitorMonitorKeyboard
Windows Server 2012 Samsung S22B300 22' ViewSonic VA703B 17" CM Quickfire TK 
PowerCaseMouse
Corsair HX850 NZXT Phantom Mionix Naos 3200 
  hide details  
Reply
post #3 of 14
Thread Starter 
I can't use external libraries, it has to be ANSI C. I'm practicing for an ACM contest.
post #4 of 14
Only option that comes to my head is working with strings, of course you will need to program the multiplication manually.
First Build
(17 items)
 
  
CPUMotherboardGraphicsRAM
i7-2600k @4.5Ghz Gigabyte Z68X-UD7 B3 MSI 6950 G.Skill Sniper 2x4GB 
Hard DriveHard DriveHard DriveCooling
Crucial M4 64GB Samsung SpinPoint 250GB Hitachi 1TB Noctua NH-D14 
OSMonitorMonitorKeyboard
Windows Server 2012 Samsung S22B300 22' ViewSonic VA703B 17" CM Quickfire TK 
PowerCaseMouse
Corsair HX850 NZXT Phantom Mionix Naos 3200 
  hide details  
Reply
First Build
(17 items)
 
  
CPUMotherboardGraphicsRAM
i7-2600k @4.5Ghz Gigabyte Z68X-UD7 B3 MSI 6950 G.Skill Sniper 2x4GB 
Hard DriveHard DriveHard DriveCooling
Crucial M4 64GB Samsung SpinPoint 250GB Hitachi 1TB Noctua NH-D14 
OSMonitorMonitorKeyboard
Windows Server 2012 Samsung S22B300 22' ViewSonic VA703B 17" CM Quickfire TK 
PowerCaseMouse
Corsair HX850 NZXT Phantom Mionix Naos 3200 
  hide details  
Reply
post #5 of 14
Quote:
Originally Posted by Barbaroti View Post

Only option that comes to my head is working with strings, of course you will need to program the multiplication manually.

Yup, I believe you are correct. Basically, start with a string of your base, and go through each index from right to left. Store the (doubled number % 10 + carry) into the same slot and, if the number was >= 5, add a carry to the next number. It shouldn't be that hard to code and will allow you to use more than the long type can hold.
Workstation
(19 items)
 
  
CPUMotherboardGraphicsGraphics
Intel i7 920 c0 @ 3.50 Asus Sabertooth X58 Nvidia gtx 570 Nvidia gtx 210 
RAMHard DriveOptical DriveOptical Drive
12 GB (Patriot 4GB DDR3 1600 Mhz + G.Skill Ripj... OCZ Vertex II 60GB + x2 WD 1TB + WD 500 GB Lite-On DVD Burner LG Blu Ray Burner 
OSMonitorMonitorMonitor
Windows 8 Professional x64, Arch Linux x64 Samsung 22 inch 1920x1080 60Hz Asus 23 inch 1920x1080 IPS Acer 19 inch 1600x900 
KeyboardPowerCaseMouse
Logitech g11 Corsair 750 Watt NZXT Tempest Razer deathadder 3500 dpi 
Mouse PadAudioAudio
OCZ Audigy SE Sony MDR-V6 
  hide details  
Reply
Workstation
(19 items)
 
  
CPUMotherboardGraphicsGraphics
Intel i7 920 c0 @ 3.50 Asus Sabertooth X58 Nvidia gtx 570 Nvidia gtx 210 
RAMHard DriveOptical DriveOptical Drive
12 GB (Patriot 4GB DDR3 1600 Mhz + G.Skill Ripj... OCZ Vertex II 60GB + x2 WD 1TB + WD 500 GB Lite-On DVD Burner LG Blu Ray Burner 
OSMonitorMonitorMonitor
Windows 8 Professional x64, Arch Linux x64 Samsung 22 inch 1920x1080 60Hz Asus 23 inch 1920x1080 IPS Acer 19 inch 1600x900 
KeyboardPowerCaseMouse
Logitech g11 Corsair 750 Watt NZXT Tempest Razer deathadder 3500 dpi 
Mouse PadAudioAudio
OCZ Audigy SE Sony MDR-V6 
  hide details  
Reply
post #6 of 14
Thread Starter 
This means I have to use arrays, right?
post #7 of 14
Pretty much, yeah. Arrays/String is the only option for numbers with the amount of digits you need.
First Build
(17 items)
 
  
CPUMotherboardGraphicsRAM
i7-2600k @4.5Ghz Gigabyte Z68X-UD7 B3 MSI 6950 G.Skill Sniper 2x4GB 
Hard DriveHard DriveHard DriveCooling
Crucial M4 64GB Samsung SpinPoint 250GB Hitachi 1TB Noctua NH-D14 
OSMonitorMonitorKeyboard
Windows Server 2012 Samsung S22B300 22' ViewSonic VA703B 17" CM Quickfire TK 
PowerCaseMouse
Corsair HX850 NZXT Phantom Mionix Naos 3200 
  hide details  
Reply
First Build
(17 items)
 
  
CPUMotherboardGraphicsRAM
i7-2600k @4.5Ghz Gigabyte Z68X-UD7 B3 MSI 6950 G.Skill Sniper 2x4GB 
Hard DriveHard DriveHard DriveCooling
Crucial M4 64GB Samsung SpinPoint 250GB Hitachi 1TB Noctua NH-D14 
OSMonitorMonitorKeyboard
Windows Server 2012 Samsung S22B300 22' ViewSonic VA703B 17" CM Quickfire TK 
PowerCaseMouse
Corsair HX850 NZXT Phantom Mionix Naos 3200 
  hide details  
Reply
post #8 of 14
Hi Icekilla,
many years ago I wrote simulation of four arithmetic operations MUL, SUB, ADD, DIV using strings, thus achieving up to 16000+ digits long numbers, of course using C this limitation is down.

Keep in mind I have written this simulation back in 1990 using QuickBasic 4.0.
I have been too lazy to rewrite it but it is so simple/straightforward that it can be easily rewritten in C.
The drawback is that executables are 16bit.

My tool (sources included) is freely downloadable at:
www.sanmayce.com/Downloads/calculator_BIG_multiplication_power.zip
Code:
D:\DOWNLO~1\_262B0~1>dir

11/02/2012  09:08 PM            65,114 calculator_BIG_multiplication_power.zip
09/19/2012  09:17 PM            41,296 calculator_mule.exe
09/19/2012  09:24 PM            41,504 calculator_stepen.exe
09/19/2012  09:24 PM            15,590 POWER.BAS
09/19/2012  09:17 PM            15,478 RTHMTC.BAS

Two quick-tests:
Code:
D:\DOWNLO~1\_262B0~1>calculator_stepen.exe
Number: 2
Power: 8192
10907481356194159294629842447337828624482641619962326924318327861897213318491192
95216264234525201987223957291796157025273109870820177184063610979765077554799078
90629884219298953860982522804820515969685161359163819677188654260932456012129055
39018863010179002525357999172000100796000265358368009052978058809523505016301954
75653911005312364560014847426035293551245843928918752768696279344088055617515694
34994540667782514081490061610592025643850457801332649356583604724240738244281224
51315177575191648992263657437224322773680750276278830452065017927617009456991684
97257879683851737049996900961120515655050115561271491492515342105748966629547032
78632150573082843022166497032439613863525162640951616800542762343599630892169144
61811874063953106654048857394348328774281674074953709935118687563599703901170218
23616749458620969857006263612082706715408157066575137281027022310927564910276759
16052087830463241104936456875492096732298245918476342738379027244843801852697776
49410727156115804346908274593399919614142427414105991174260605564837637563145276
11362658628383368621157993638020878537675545336789915694234433955666315070087213
53547025567031200413072549583450835743965382893607708097855057891296790735278005
49356215610907958451729541159729274798775277385600082041185589300047777487277618
53813510493840581861598652211605960308356405941821189714037868726219481498727603
65361629885617482241303348543878532402475141941718301228107820972930353737280457
43720952287036227763639452908698062584223551485075710396193874496298668081887696
62815778153079393179093143648340761738581819563002994422790754955061288818308430
07964869323217915876591803556521615711540299212027615560787310793747746684152836
29877086994501520312318625942030856938389446570613462367042340268211029589549511
97087076546186622796294536451620756509351018906023773821539532776208676978589731
96633030889330466516943618507835064156833694453005143749131129883436726523859540
49042734559287239495252271846174043678547546104743770197680255766058810380772707
07717942221977090385438585844095492116099852538903974655703943973086090930596963
36076752996493841459818570596375456149735582781362383328890630900428801732142480
86639626713335280092327583508730596141187237814221014601986157473868550968960891
89180441339558524822867541113212638793675567650340362970031930023397828465318547
23824423202801518968966041882297600081543761065225427016359565087543385114712321
4227266605403581781469090806576468950587661997186505665475715792896

D:\DOWNLO~1\_262B0~1>calculator_stepen.exe
Number: 4
Power: 4096
10907481356194159294629842447337828624482641619962326924318327861897213318491192
95216264234525201987223957291796157025273109870820177184063610979765077554799078
90629884219298953860982522804820515969685161359163819677188654260932456012129055
39018863010179002525357999172000100796000265358368009052978058809523505016301954
75653911005312364560014847426035293551245843928918752768696279344088055617515694
34994540667782514081490061610592025643850457801332649356583604724240738244281224
51315177575191648992263657437224322773680750276278830452065017927617009456991684
97257879683851737049996900961120515655050115561271491492515342105748966629547032
78632150573082843022166497032439613863525162640951616800542762343599630892169144
61811874063953106654048857394348328774281674074953709935118687563599703901170218
23616749458620969857006263612082706715408157066575137281027022310927564910276759
16052087830463241104936456875492096732298245918476342738379027244843801852697776
49410727156115804346908274593399919614142427414105991174260605564837637563145276
11362658628383368621157993638020878537675545336789915694234433955666315070087213
53547025567031200413072549583450835743965382893607708097855057891296790735278005
49356215610907958451729541159729274798775277385600082041185589300047777487277618
53813510493840581861598652211605960308356405941821189714037868726219481498727603
65361629885617482241303348543878532402475141941718301228107820972930353737280457
43720952287036227763639452908698062584223551485075710396193874496298668081887696
62815778153079393179093143648340761738581819563002994422790754955061288818308430
07964869323217915876591803556521615711540299212027615560787310793747746684152836
29877086994501520312318625942030856938389446570613462367042340268211029589549511
97087076546186622796294536451620756509351018906023773821539532776208676978589731
96633030889330466516943618507835064156833694453005143749131129883436726523859540
49042734559287239495252271846174043678547546104743770197680255766058810380772707
07717942221977090385438585844095492116099852538903974655703943973086090930596963
36076752996493841459818570596375456149735582781362383328890630900428801732142480
86639626713335280092327583508730596141187237814221014601986157473868550968960891
89180441339558524822867541113212638793675567650340362970031930023397828465318547
23824423202801518968966041882297600081543761065225427016359565087543385114712321
4227266605403581781469090806576468950587661997186505665475715792896

D:\DOWNLO~1\_262B0~1>

Enjoy!
Edited by Sanmayce - 11/2/12 at 12:10pm
post #9 of 14
I'm not sure, but maybe a
Code:
unsigned long double
?
Or a
Code:
unsigned long long
?
post #10 of 14
Quote:
Originally Posted by 3930K View Post

...
Code:
unsigned long double
?

No chance in ANSI C.
Ol' Sandy
(30 items)
 
"Zeus"
(13 items)
 
 
CPUMotherboardGraphicsRAM
Intel Core i5 2500K (4.5ghz @ 1.320v) Gigabyte Z68X-UD3R-B3 MSI R7970 Lightning Corsair 16GB (4x4GB) 
Hard DriveHard DriveHard DriveHard Drive
Plextor PX-256M5S 256GB Samsung EVO 1TB Hitachi HDS721010CLA332 Hitachi HDS723020BLA642 
Hard DriveHard DriveHard DriveOptical Drive
Hitachi HDS723020BLA642 Hitachi HUA722010CLA330 WDC WD10EARS-00Z5B1 TSSTcorp CDDVDW SH-S223B 
CoolingCoolingOSMonitor
Phanteks PH-TC14PE with TY-140's Lamptron FCv5 (x2) Windows 8 Pro 64-bit Dell U2412M 
MonitorMonitorMonitorKeyboard
Dell U2412M Dell U2212HM Dell U2713HM Topre Realforce 87UB | Ducky DK9087 G2 Pro 
PowerCaseMouseMouse Pad
Corsair AX-750 Corsair Obsidian 650D Logitech G700 XTRAC Ripper XXL 
AudioAudioAudioAudio
Westone W3 IEMs RE-272 IEMs Shure SE-215 IEMs Schiit Bifrost DAC 
AudioAudio
Schiit Asgard 2 amp HiVi Swan M50W 2.1 
CPUMotherboardRAMHard Drive
Intel Xeon E5-2620 Super Micro X9SRL-F-B 64GB 1333MHz 4x WD RE4 1TB on-host (Adaptec 6805E RAID 10) 
Optical DriveOSPowerCase
2x Crucial M500 480GB, 2x WD RE4 500GB on-host ... Windows Server 2012 R2 x64 SeaSonic SS-400FL2 Fractal Define R3 
CPUMotherboardGraphicsRAM
Intel Core i5-3437U HP EliteBook Folio 9470m  Intel HD Graphics 4000  16GB DDR3 SDRAM 
Hard DriveOS
256GB SSD elementaryOS "Luna" 
  hide details  
Reply
Ol' Sandy
(30 items)
 
"Zeus"
(13 items)
 
 
CPUMotherboardGraphicsRAM
Intel Core i5 2500K (4.5ghz @ 1.320v) Gigabyte Z68X-UD3R-B3 MSI R7970 Lightning Corsair 16GB (4x4GB) 
Hard DriveHard DriveHard DriveHard Drive
Plextor PX-256M5S 256GB Samsung EVO 1TB Hitachi HDS721010CLA332 Hitachi HDS723020BLA642 
Hard DriveHard DriveHard DriveOptical Drive
Hitachi HDS723020BLA642 Hitachi HUA722010CLA330 WDC WD10EARS-00Z5B1 TSSTcorp CDDVDW SH-S223B 
CoolingCoolingOSMonitor
Phanteks PH-TC14PE with TY-140's Lamptron FCv5 (x2) Windows 8 Pro 64-bit Dell U2412M 
MonitorMonitorMonitorKeyboard
Dell U2412M Dell U2212HM Dell U2713HM Topre Realforce 87UB | Ducky DK9087 G2 Pro 
PowerCaseMouseMouse Pad
Corsair AX-750 Corsair Obsidian 650D Logitech G700 XTRAC Ripper XXL 
AudioAudioAudioAudio
Westone W3 IEMs RE-272 IEMs Shure SE-215 IEMs Schiit Bifrost DAC 
AudioAudio
Schiit Asgard 2 amp HiVi Swan M50W 2.1 
CPUMotherboardRAMHard Drive
Intel Xeon E5-2620 Super Micro X9SRL-F-B 64GB 1333MHz 4x WD RE4 1TB on-host (Adaptec 6805E RAID 10) 
Optical DriveOSPowerCase
2x Crucial M500 480GB, 2x WD RE4 500GB on-host ... Windows Server 2012 R2 x64 SeaSonic SS-400FL2 Fractal Define R3 
CPUMotherboardGraphicsRAM
Intel Core i5-3437U HP EliteBook Folio 9470m  Intel HD Graphics 4000  16GB DDR3 SDRAM 
Hard DriveOS
256GB SSD elementaryOS "Luna" 
  hide details  
Reply
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Coding and Programming
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › High-precision program that calculates 2^n