429,374 Members | 1,768 Online
Need help? Post your question and get tips & solutions from a community of 429,374 IT Pros & Developers. It's quick & easy.

factorial and exponent

 P: n/a I want to calculate the value of 126 raise to the power 126 in turbo C. I've checked it with unsigned long int but it doesn't help. So how could one calculate the value of such big numbers? What's the technique? Jun 16 '07 #1
23 Replies

 P: n/a "Thomas" I want to calculate the value of 126 raise to the power 126 in turbo C. I've checked it with unsigned long int but it doesn't help. So how could one calculate the value of such big numbers? What's the technique? 1. Use another programming language, or 2. find a bignum library, or 3. don't compute it. Compute its base-10 log. The integer part will be the exponent, and from the fractional part you can find out the mantissa. printf("%fe%d", pow(10, x - floor(x)), (int)floor(x)); where x is 126 * log10(126). HTH. Jun 16 '07 #2

 P: n/a In this article, I use ^ to represent "to the power of", rather than as XOR. Thomas said: I want to calculate the value of 126 raise to the power 126 in turbo C. 44329076602207821491972574571700100562486647339617 150064334557177890\ 43517106373872170818953941792055669609014893218047 089803712563472169\ 06583373889953014265747680923405829337012685381706 863104615274196776\ 39132400195465417937691907225941135755503122280004 52759781376 I've checked it with unsigned long int but it doesn't help. Since the largest value you are likely to be able to store in an unsigned long int in Turbo C is 4294967295, it's hardly surprising that you can't represent 126^126 in that type. So how could one calculate the value of such big numbers? What's the technique? How would you do it by hand? To save you some work, you'd probably start off by observing that 126^126 = (126^63)^2 = ((126^31)^2*126)^2 = (((126^15)^2*126)^2*126)^2 = ((((126^7)^2*126)^2*126)^2*126)^2 = (((((126^3)^2*126)^2*126)^2*126)^2*126)^2 = ((((((126^2)*126)^2*126)^2*126)^2*126)^2*126)^2 So if you can multiply a number by itself, and multiply a number by 126, you can get your result quite quickly. See Knuth's "The Art of Computer Programming", volume 2, for information on how to multiply two arbitrarily large numbers. Alternatively, learn how to use GNU's GMP package, or Miracl, both of which have C bindings. -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at the above domain, - www. Jun 16 '07 #3

 P: n/a Thomas wrote: > I want to calculate the value of 126 raise to the power 126 in turbo C. I've checked it with unsigned long int but it doesn't help. So how could one calculate the value of such big numbers? What's the technique? First, decide what holds the answer. You will need in the order of 1000 bits. Probably at least two of them. -- cbfalconer at maineline dot net -- Posted via a free Usenet account from http://www.teranews.com Jun 16 '07 #4

 P: n/a On Jun 16, 5:02 pm, Thomas

 P: n/a BiGYaN said: On Jun 16, 5:02 pm, Thomas I want to calculate the value of 126 raise to the power 126 in turboC.I've checked it with unsigned long int but it doesn't help.So how could one calculate the value of such big numbers?What's the technique? Use GMP library found in http://gmplib.org/ It will enable you to do "Arithmetic without Limitations" !! Nonsense. Consider an integer greater than or equal to 2. Call it A. Consider another integer greater than or equal to 2. Call it B. Raise A to the power B, storing the result in A. Now raise B to the power A, storing the result in B. If you repeat this often enough, you *will* hit a limit, no matter what numerical library you use. -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at the above domain, - www. Jun 17 '07 #6

 P: n/a "Richard Heathfield" On Jun 16, 5:02 pm, Thomas >I want to calculate the value of 126 raise to the power 126 in turboC.I've checked it with unsigned long int but it doesn't help.So how could one calculate the value of such big numbers?What's the technique? Use GMP library found in http://gmplib.org/It will enable you to do "Arithmetic without Limitations" !! Nonsense. Consider an integer greater than or equal to 2. Call it A. Consider another integer greater than or equal to 2. Call it B. Raise A to the power B, storing the result in A. Now raise B to the power A, storing the result in B. If you repeat this often enough, you *will* hit a limit, no matter what numerical library you use. But it is a limit of your computer, not of the library itself. Jun 17 '07 #7

 P: n/a Army1987 wrote, On 17/06/07 09:48: "Richard Heathfield" BiGYaN said: >>On Jun 16, 5:02 pm, Thomas

 P: n/a Army1987 said: "Richard Heathfield" BiGYaN said: >>>Use GMP library found in http://gmplib.org/It will enable you to do "Arithmetic without Limitations" !! Nonsense.Consider an integer greater than or equal to 2. Call it A. Consideranother integer greater than or equal to 2. Call it B.Raise A to the power B, storing the result in A. Now raise B to thepower A, storing the result in B. If you repeat this often enough,you *will* hit a limit, no matter what numerical library you use. But it is a limit of your computer, not of the library itself. Nevertheless, it is a limit, and therefore the library *cannot* 'enable you to do "Arithmetic without Limitations"', and therefore BiGYaN's statement is nonsense. Incidentally, you've just emerged from a 30-day spell in my sin bin. I hope I won't have to chuck you back in there. -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at the above domain, - www. Jun 17 '07 #9

 P: n/a On Jun 17, 12:50 pm, Richard Heathfield

 P: n/a Richard Heathfield wrote: Army1987 said: >"Richard Heathfield" >BiGYaN said: >>>Use GMP library found in http://gmplib.org/It will enable you to do "Arithmetic without Limitations" !!Nonsense.Consider an integer greater than or equal to 2. Call it A. Consideranother integer greater than or equal to 2. Call it B.Raise A to the power B, storing the result in A. Now raise B to thepower A, storing the result in B. If you repeat this often enough,you *will* hit a limit, no matter what numerical library you use. But it is a limit of your computer, not of the library itself. Nevertheless, it is a limit, and therefore the library *cannot* 'enable you to do "Arithmetic without Limitations"', and therefore BiGYaN's statement is nonsense. Incidentally, you've just emerged from a 30-day spell in my sin bin. I hope I won't have to chuck you back in there. Of course there are limits, but I don't agree that they necessarily have to be in the library. size_t is one limit, but if run on for example a windows box it will not be *the* limit. A win32 application is not allowed to allocate more than 2Gbytes of memory (and that's typically half of what size_t allows for), unless you buy a more expensive version of windows where that limit is raised to 3Gbytes. It would also be possible for the mathematics library to internally use something else than a standard C pointer and internally use paging towards the system's hard disk or some internet based server or whatever (magnetic tape?) allowing for a *much* higher limit. Oh well the limit will still be there somewhere, but the calculation time will probably be the limiting factor instead... No, I don't seriously suggest using magnetic tape as a paging media... but it would be possible! Jun 17 '07 #11

 P: n/a Richard Heathfield wrote: Army1987 said: >"Richard Heathfield" >BiGYaN said: >>>Use GMP library found in http://gmplib.org/It will enable you to do "Arithmetic without Limitations" !!Nonsense.Consider an integer greater than or equal to 2. Call it A. Consideranother integer greater than or equal to 2. Call it B.Raise A to the power B, storing the result in A. Now raise B to thepower A, storing the result in B. If you repeat this often enough,you *will* hit a limit, no matter what numerical library you use. But it is a limit of your computer, not of the library itself. Nevertheless, it is a limit, and therefore the library *cannot* 'enable you to do "Arithmetic without Limitations"', and therefore BiGYaN's statement is nonsense. Of course there are limits, but I don't agree that they necessarily have to be in the library. size_t is one limit, but if run on for example a windows box it will not be *the* limit. A win32 application is not allowed to allocate more than 2Gbytes of memory (and that's typically half of what size_t allows for), unless you buy a more expensive version of windows where that limit is raised to 3Gbytes. It would also be possible for the mathematics library to internally use something else than a standard C pointer and internally use paging towards the system's hard disk or some internet based server or whatever (magnetic tape?) allowing for a *much* higher limit. Oh well the limit will still be there somewhere, but the calculation time will probably be the limiting factor instead... No, I don't seriously suggest using magnetic tape as a paging media... but it would be possible! Jun 17 '07 #12

 P: n/a BiGYaN said: On Jun 17, 12:50 pm, Richard Heathfield BiGYaN said: Use GMP library found inhttp://gmplib.org/ It will enable you to do "Arithmetic without Limitations" !! Nonsense.Consider an integer greater than or equal to 2. Call it A. Consideranother integer greater than or equal to 2. Call it B.Raise A to the power B, storing the result in A. Now raise B to thepower A, storing the result in B. If you repeat this often enough,you *will* hit a limit, no matter what numerical library you use. "Arithmetic without Limitations" is sort of a slogan for GMP (http:// gmplib.org/). That's why I just put it in quotes. It's still false, within quotes or without them. The case that you are talking about does not show the limitation of the numerical library. It's a limit of your computer. It's still a limit. Besides, for all *practical purposes* you won't hit this limit in a modern computer. It's still a limit. Like I'm quite sure that nobody will actually need all the digits of 126^126 for any *practical* job. Cryptography springs to mind as a practical application which requires exactness to the very last digit for calculations involving numbers of that size and indeed greater. -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at the above domain, - www. Jun 18 '07 #13

 P: n/a Johan Bengtsson said: Of course there are limits, but I don't agree that they necessarily have to be in the library. I'm not saying they are, but that's not the issue. The claim was that the library allows you to do arithmetic without limitations, and all I'm saying is that that claim is false. -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at the above domain, - www. Jun 18 '07 #14

 P: n/a On Jun 18, 8:44 am, Richard Heathfield

 P: n/a "Richard Heathfield" "Richard Heathfield" >BiGYaN said: >>>>Use GMP library found in http://gmplib.org/It will enable you to do "Arithmetic without Limitations" !!Nonsense.Consider an integer greater than or equal to 2. Call it A. Consideranother integer greater than or equal to 2. Call it B.Raise A to the power B, storing the result in A. Now raise B to thepower A, storing the result in B. If you repeat this often enough,you *will* hit a limit, no matter what numerical library you use. But it is a limit of your computer, not of the library itself. Nevertheless, it is a limit, and therefore the library *cannot* 'enable you to do "Arithmetic without Limitations"', and therefore BiGYaN's statement is nonsense. If you cannot compute a number n with a computer, you can always (at least in principle) use a computer with a larger size_t and compute it. Your statement is much like "You cannot use the long division algorithm indefinitely because sooner or later you'll run out of paper", or "There is a N such as you cannot draw a regular (2^N * 3 * 5 * 17 * 257 * 65537)-gon with straightedge and compass, because even if the polygon were as large as the universe, each side would need to be shorter than a Planck length". The library does enable Arithmetic without Limitations. It is the implementation (and the universe) which put the limits. Jun 24 '07 #16

 P: n/a On Jun 24, 11:17 am, "Army1987"

 P: n/a On Jun 24, 11:46 am, JT

 P: n/a "JT" If you cannot compute a number n with a computer, you can always(at least in principle) use a computer with a larger size_t andcompute it.Your statement is much like "You cannot use the long divisionalgorithm indefinitely because sooner or later you'll run out ofpaper", or "There is a N such as you cannot draw a regular(2^N * 3 * 5 * 17 * 257 * 65537)-gon with straightedge and compass,because even if the polygon were as large as the universe, eachside would need to be shorter than a Planck length". >The library does enable Arithmetic without Limitations. It is theimplementation (and the universe) which put the limits. [snip] My two objections: (1) That library does not "enable" unlimited arithmetic. The library itself does not "impose" additional limit. (2) People are confused between infinite, and finite unbounded. People should read more math books. [correction incorporated above] Indeed, I'm not saying that "Arithmetic without Limitations" means that the library allows arithmetic with transfinite cardinals, only that it allows arithmetic with arbitrarily large natural (finite) numbers. If there are indeed limits, they are due to the implementation. Wait for a computer with more memory, and you'll be able to compute larger numbers. By your argument, the long division algorithm does not "enable" you to divide arbitrarily large numbers, it just doesn't "impose" additional limit (to that dictated by the size of the paper sheet you work on). Jun 24 '07 #19

 P: n/a Army1987 said: "Richard Heathfield" ha scritto... >Army1987 said: >>"Richard Heathfield" ha scritto... >>>Raise A to the power B, storing the result in A. Now raise B to thepower A, storing the result in B. If you repeat this often enough,you *will* hit a limit, no matter what numerical library you use.But it is a limit of your computer, not of the library itself. Nevertheless, it is a limit, and therefore the library *cannot*'enable you to do "Arithmetic without Limitations"', and thereforeBiGYaN's statement is nonsense. If you cannot compute a number n with a computer, you can always (at least in principle) use a computer with a larger size_t and compute it. No, in principle you'll run out of resources at some point. Your statement is much like "You cannot use the long division algorithm indefinitely because sooner or later you'll run out of paper", Correct. or "There is a N such as you cannot draw a regular (2^N * 3 * 5 * 17 * 257 * 65537)-gon with straightedge and compass, because even if the polygon were as large as the universe, each side would need to be shorter than a Planck length". Correct. The library does enable Arithmetic without Limitations. No, it doesn't. To do so, it would have to remove all limitations on arithmetic, and it simply can't. It is the implementation (and the universe) which put the limits. And therefore the limits are there. If the library does not remove them, it does not enable arithmetic without limits. -- Richard Heathfield Email: -www. +rjh@ Google users: "Usenet is a strange place" - dmr 29 July 1999 Jun 24 '07 #20

 P: n/a "Richard Heathfield" or "There is a N such as you cannot draw a regular(2^N * 3 * 5 * 17 * 257 * 65537)-gon with straightedge and compass,because even if the polygon were as large as the universe, eachside would need to be shorter than a Planck length". Correct. So references which claim that a regular polygon of n sides is constructible if and only if all the odd prime factors of n are distinct Fermat primes (e.g. Wikipedia) must be wrong, since 2^100000000 * 3 * 17 * 257 is such a number, but such a polygon cannot be constructed. :-) (Or the limits of an algorithm are not the same thing as the limits of its implementation, nor even the same thing as the limits of the universe.) Jun 24 '07 #21

 P: n/a Army1987 said: So references which claim that a regular polygon of n sides is constructible if and only if all the odd prime factors of n are distinct Fermat primes (e.g. Wikipedia) must be wrong, since 2^100000000 * 3 * 17 * 257 is such a number, but such a polygon cannot be constructed. :-) That depends on their definition of "constructible". As for Wikipedia being wrong, that wouldn't particularly shock me. -- Richard Heathfield Email: -www. +rjh@ Google users: "Usenet is a strange place" - dmr 29 July 1999 Jun 24 '07 #22

 P: n/a On Jun 16, 7:02 am, Thomas

 P: n/a Tom Gear wrote On 06/27/07 14:21,: On Jun 16, 7:02 am, Thomas >I want to calculate the value of 126 raise to the power 126 in turboC.I've checked it with unsigned long int but it doesn't help.So how could one calculate the value of such big numbers?What's the technique? Hi. This is similar to a programming project I'm doing in assembler. I think the first thing you need to do, and I think someone else mentioned this, is to find out the size of the final result. Then make sure you feed the result there. You do this by using natural logarithms, but I forget how, I had to ask my son. Convert 126^126 base ten = 2^ whatever. You should be able to do this in your head, to a reasonable approximation. lg(126^126) = 126*lg(126) ~= 126*lg(128) = 126 * 7 = 882 Replacing 126 by 128 errs on the high side, so the approximation cannot be too small. (It turns out -- I cheated and used a calculator -- that 880 bits will suffice; the estimate is high by <0.23%.) I think you might consider bit shifting since 126 = 128 - 2. [...] See TAOCP section 4.6.3 for efficient computation of powers. -- Er*********@sun.com Jun 27 '07 #24