Factorial resolving more efficiiently

[Satan]

Okay so we know that Arithmetic operations such as addition and subtraction are a set of rules built by humans to interpret how a given set of operands are handled.

Now using addition and subtraction as base we got multiplication and division. I believe computers multiply and divide by repeatedly adding and subtracting (do correct me if I'm wrong).

Similarly orders can be solved by repeated multiplication.

Now let's consider factorials (n!). If you don't know what a factorial is, it's an operation like addition and subtraction but a bit different.

A factorial of a number is multiplication of natural numbers till the 'nth' specified number.

So factorial of 2 (2!) = 1x2 = 2
3 (3!) = 1x2x3 = 6
4 (4!) = 1x2x3x4 = 24 and so on..


So if you had to write a computer program to solve factorials, it would multiply numbers to nth number and solve from there.

So if I gave my program 6!x4!, it would solve (1x2x3x4x5x6)x(1x2x3x4)

BUT!
That can be very time consuming for larger numbers.


Assume that we're creating a program that solves factorials. So we have a factorial and arithmetic parser.

So now I was thinking that because every factorial has a fixed value, we could directly assign the value to it instead of solving for the value.
(What's an efficient way to do this?) - maybe something with arrays

And also, what if we did not have to do with these values at all!?

What if we could define our own Arithmetic like addition?

So I was thinking instead of assigning 2! and 4! and then resolving 2!x4! we could have the compiler refer the table for what 2!x4! would result with.

Likewise for addition, subtraction, multiplication, division etc.
-> I was thinking about maybe 2D arrays.
-> This can be useful because large factorials like 25! are so huge that they cannot be supported by C++ alone.


Thanks for reading!

[kbw]

So I was thinking instead of assigning 2! and 4! and then resolving 2!x4! we could have the compiler refer the table for what 2!x4! would result with.

It's also the kind of thing a compiler can do if it was a frequent requirement.

It's common enough for the compiler to perform basic arithmetic. For example:

int main() {
        return 2*3;
}

generates:

0000000000000000 <main>:
   0:   55                      push   %rbp
   1:   48 89 e5                mov    %rsp,%rbp
   4:   b8 06 00 00 00          mov    $0x6,%eax
   9:   c7 45 fc 00 00 00 00    movl   $0x0,-0x4(%rbp)
  10:   5d                      pop    %rbp
  11:   c3                      retq

I've highlighted the 2x3 in the code, the compiler resolved that to 6.

Just so you know, macros and templates can generate such code at compile time too. For example:

template <unsigned int n>
struct factorial {
	enum { value = n * factorial<n - 1>::value };
};

template <>
struct factorial<0> {
	enum { value = 1 };
};

https://en.wikipedia.org/wiki/Template_metaprogramming

[Satan]

So in the example using template, when the program calculates say the factorial is 30, would it know the factorial of 24 beforehand it were to be asked for it?

[kbw]

Have you read the link?

The compiler calculates the value at compile time uses places the value directly, in much the same way the code I posted above evaluates 2x3 uses places 6 in its place.

If you want a factorial table, you can build one at compile time using this method.

[Satan]

Let's keep that as one option although I still didn't understand what the template example does [more importantly how it works, I get that it finds factorial before hand but where is the input?] and what you meant by 2x3 evaluates to 6.. that is multiplication I didn't get the link. If that is supposed to be 3! then I have told you that I want to find a way that avoids multiplication.

Anyways for large numbers like 29 you cannot rely on compile time processing either. One it is going to be time consuming and inefficient, Two even long long int cannot store such large numbers (like factorial of 29!).

But if we wrote a table for say subtraction of factorials then we could find the value of 29! - 27! by finding their intersection in a 2D array (like how we have a table for multiplication, where the intersection is the answer) we could solve big factorials.

Of course if it's like 29! - 2! we can just keep it as undefined or further parse it with other elements.


Lastly @kbw, why does compile time and run time make difference if they're doing the same task? They're gonna take the same time to process aren't they? If not compile time must be more inefficient because it is finding factorials of non-used factors. I just didn't get why we're using compile time!

For filling the table of course I will have to solve factorials, but then again why the heck would compile time be more useful even in this case?

Even for filling the table I think it's a better idea to rely on online websites that can handle large numbers unlike c++ STL.

Thanks for reading

[kbw]

Let's keep that as one option although I still didn't understand what the template example does [more importantly how it works, I get that it finds factorial before hand but where is the input?

The input is where you use it in your code.

and what you meant by 2x3 evaluates to 6.. that is multiplication I didn't get the link. If that is supposed to be 3! then I have told you that I want to find a way that avoids multiplication.

I demonstrated that the compiler has a precedent of doing arithmetic rather than deferring it to a run-time calculation. I showed the source input in C and the compiled output in assembler.

I then went on to demonstrate how operations other than basic arithmetic can be generated at compile time, using factorial as the example.

Anyways for large numbers like 29 you cannot rely on compile time processing either. One it is going to be time consuming and inefficient, Two even long long int cannot store such large numbers (like factorial of 29!).

I agree 29! is a large number. That aside, I don't know what you mean.

But if we wrote a table for say subtraction of factorials then we could find the value of 29! - 27! by finding their intersection in a 2D array (like how we have a table for multiplication, where the intersection is the answer) we could solve big factorials.

That sounds like an application specific thing. Again, I'm not sure what the issue is. There are bignum classes around that can handle integers beyond the range of machine word integers.

Lastly @kbw, why does compile time and run time make difference if they're doing the same task? They're gonna take the same time to process aren't they? If not compile time must be more inefficient because it is finding factorials of non-used factors. I just didn't get why we're using compile time!

For filling the table of course I will have to solve factorials, but then again why the heck would compile time be more useful even in this case?

If the task is done at compile time, the time is spend during code creation. If the task is done at runtime, it's done every time the program is run. There's a huge difference.

Even for filling the table I think it's a better idea to rely on online websites that can handle large numbers unlike c++ STL.

I don't know what you mean by online websites that can handle large numbers. Website are just published material, whether that be an API, or human consumable content. STL isn't a number type. It's an attempt to provide generic algorithms and containers that are independent of datatype in a minimal way.

Like I said, if you want larger integer types, take look at bignum implementations.

[Satan]

"I don't know what you mean by online websites that can handle large numbers."
(I would) Search online to get the values of factorials because assuming I did not use bignum I could not rely on c++ because 1) it loses precision, 2) c++ cannot handle factorials of above 20 with long long int.


It never occurred to me that I could use a non-standard library to implement a larger and more precise integer datatype, thanks!

Which library do you suggest for big nums?

"The input is where you use it in your code."
I take it that it works like #define 2! = 2 (but only the value of 2! is calculated) is that accurate?

"I agree 29! is a large number. That aside, I don't know what you mean."
29! is 29x28x27.. x2x1.
That's a big number both to hold and to calculate.

So is it really more efficient than say directly assigning values?
What is better:
#define 5! = 120
or
#define 5! = 5x4x3x2x1


Besides that, values of say factorial 29! would be so large they can't even be stored. So I thought we would make a 2D table for say 29!-28!, where we find the intersection of 29th column and 28th row to find the answer of 29!-28! (if the 2d table's intersection stand for the subtraction of the rowth from the columnth).



Instead of 2D array, we could use a library like bignum like you said, and directly assign values instead of making tables because we can hold big numbers now. It still might be less efficient but it works.

So how do we do that? #define 1! = 1 like so? Or how? (I want to cut out manually finding factorial for every number, because both #define 3! = 6 and the template give the same result)


"If the task is done at compile time, the time is spend during code creation. If the task is done at runtime, it's done every time the program is run. There's a huge difference."
What I meant was that it still evaluates the factorial which 1) can be time consuming for large numbers 2) can be so big that they can't be stored (this was the assumption when I didn't know about bignum)

See it might not be so time consuming but I thought 2D array would be more efficient.


Sorry for the confusion I hope you get what I'm trying to say now.. But feel free to ask again.

"The input is where you use it in your code."
n is the number to calculate? And then when that number is used it will be replaced by the value that the compiler had solved for?

So then why is this better than just #define 3! = 6?
Instead of using template and n as 3

I realize that a for-loop can be used so the number of lines using what you mentioned is very less compared to the hundreds of lines my suggestion would take.. but the same number of lines are being executed right.. in fact template has to evaluate instead of directly assigning. So the only reason for using the template example would be because of beautifying the code, but if that was the case why can't we just dump all the definitions to another headerfile and use #include""? ;)

Thanks for reading
I appreciate that you spent so much time in this thread trying to help me dude..

[jonnin]

is there a requirement to calculate it? I mean, 64 bits worth of factorials will fit into a very small lookup table.

eg

unsigned long long fact[] = {1,1,2,6,24,120,...};//fill in the rest
...

x = fact[10]; //pretty much instantly resolved.

it wouldnt take 5 min to write a program that generated the table as a copy and pasteable c++ statement.

it would only cost a couple more clock cycles to wrap that table in a dumb class to apply a custom ! operator if you really wanted to show off. I don't recommend this, but you could do it. Its going to make the program weird and hard to read if you use any logic operations alongside your math stuff.

[Satan]

Thanks Jonnin that's much better.

Bignums have infinite precision? cool

[jonnin]

nothing is infinite on any computer :)
most current computers support 64 bit integers. that is 2 to the 64th power as the biggest possible value. bigint is not a standard c++ type. if you need to go bigger than this, youll need to find a big integer library. You may be able to go a little farther with doubles at the risk of approximation of the values; factorials get zero value lower significant digits after a while and those pile up on the back end, doubles crop that back out due to floating point, but youll get roundoff after a while. Remember its in base 2, not 10, so the zeros on the back end are not always cropped as you might think as a human, but they are reduced.

[JLBorges]

> Bignums have infinite precision? cool

Big integers can have 'arbitrarily large precision' ie. precision limited only by the amount of available memory.

For an example of computing factorials with these, see:
http://www.cplusplus.com/forum/beginner/241506/#msg1073891

[Satan]

@jonnin but 2^64 is a 20 digit number..
JLBorge's script was able to calculate 30000! which is 121288 digits.

And wow JLBorge that's so much faster than I thought a computer could execute hehe.

[dhayden]

that's so much faster than I thought a computer could execute hehe.

I think this is your main problem. Computers are way faster than you seem to think. An ordinary consumer computer can easily do one BILLION operations per second. Calculating factorials is child's play.

I believe computers multiply and divide by repeatedly adding and subtracting

Actually, computer algorithms for arithmetic are surprisingly elaborate. They've been tuned to be fast, or take few transistors, or some combination of the two. I took an entire graduate level course on computer arithmetic in 1986.

So if I gave my program 6!x4!, it would solve (1x2x3x4x5x6)x(1x2x3x4)

BUT!
That can be very time consuming for larger numbers.

As JLBorges showed, it's actually pretty quick.

we could directly assign the value to it instead of solving for the value.

That's a very good insight (although one that others had long before you). The technique is to pre-compute the values, or some of the values. A related technique is called "memoization" where the function remembers the result each time it's called. Then if you call it with the same arguments again, it just returns the memorized value.

[jonnin]

^^^ So, more about what is happening.
The cpu itself can multiply and all that on values up to some size. A current, 64 bit processor, can, unsurprisingly, work with up to 64 bits at a time for its integer work. If you need something bigger than the CPU can handle ... the big int libraries fill the gap. They take, say, 1000 bytes and break up the math so it can be done one chunk at a time in the CPU. Its slower than working with cpu sized integers, but computers are fast enough that if you need the big values, you can use them and the results come right on through quickly.

if you have a max size of factorial you need, and its not too far out there, you can still make that lookup table of big integers. Often factorials are needed to some size and no more, eg in probability you usually only need a few small ones. If you need them for too far out, memorization is worth a look (consider a <map> of in, out). If you want the answers faster than the cpu can deliver, or you are looping with a LOT of them and need a tweak, its worth doing. That is true for any problem... solving the same problem over and over is eventually going to drag your program down while just having the answer on hand is going to speed it up. As was said, this was discovered long before even computers were ever thought up... the slide rule is nothing but a practical example of this...

[Satan]

Thanks A LOT dhayden and jonnin!

@jonnin so there's no limit to the size of integer that the compiler can handle, it's just that it takes more time. So in practice could I find the factorial of 10240250252052054250! but it would just take a lot more time?

[kbw]

Not just time, memory too. Do you realize how large the numbers you're talking about are?

[Satan]

So a computer could crash? How do I limit CPU usage? So that I can find the factorial of that number with an acceptable CPU usage?


edit: In Visual studios no matter what kind of operation I put the CPU doesn't exceed 25% CPU and process memory keeps increasing. (999999999999999999999999999 to the power 100)

But still is there a way to "limit" CPU usage inside the program itself?

[dhayden]

no matter what kind of operation I put the CPU doesn't exceed 25% CPU

I'm going to guess that you have a quad-core system. You're using 100% of one core's capability, which is 25% of the total capability of all 4 CPUs.

is there a way to "limit" CPU usage inside the program itself?

Sometimes, but that is an operating-system specific and I'm not familiar with windows programming.

How many digits are in a factorial? Use lgamma() and some math to compute that. 1,000,000,000! has about 8.5 billion digits. So you'd need more than 8GB on your system just to store the number in RAM. 5,000,000,000! is more than 46 billion digits and probably exceeds the RAM in your system.

#include <iostream>
#include <math.h>
#include <cstdlib>

using std::atoi;
using std::cout;

int
main(int argc, char *argv[])
{
    double x = atof(argv[1]);
    double y = lgamma(x+1);	// ln(X!) = lgamma(X+1)

    double digits = ceil(y / log(10.0));
    cout << x << "! has about " << digits << " digits\n";
}

[Satan]

@dhayden that's cool!
But 1GB is 1billion bytes. So you're saying that bignum is taking 1byte per digit? That's a bit expensive compared to int data type. But I get that it's like char.

So just out of curiosity, how would you be more efficient with this or is there a more efficient implementation for bignum? Like for example convert bignum (assuming there's no better way of implementing bignums) to int if it's within int limits, would that be a good idea? Because we're trying to preserve RAM.

Also likewise is it possible to limit RAM usage on the program by declaring the limit within the program?


How do websites process big arithmetics like this? Do they just have large computers or is there also a secret (purely out of curiosity)?

[JLBorges]

> So you're saying that bignum is taking 1byte per digit?
> That's a bit expensive compared to int data type. But I get that it's like char.

No, a reasonable implementation would not be using one byte per digit;
in addition to wasting memory, it would also make calculations inefficient.
Most implementations would use an internal binary representation, akin to the built-in integer types.

#include <iostream>
#include <limits>
#include <cstdint>
#include <boost/multiprecision/cpp_int.hpp>

int main()
{
    using namespace boost::multiprecision ;

    constexpr std::size_t NBITS = 1'000'000 ;
    using big_int_type = number< cpp_int_backend< NBITS, NBITS, unsigned_magnitude, unchecked, void > > ;
    
    std::cout << "buit-in integer with " << 64 << " bits of precision uses " << sizeof(std::uint64_t) << " bytes\n"
              << "and can hold numbers having up to " << std::numeric_limits<std::uint64_t>::digits10 << " decimal digits\n\n" ;
    

    std::cout << "big integer with " << NBITS << " bits of precision uses " << sizeof(big_int_type) << " bytes\n"
              << "and can hold numbers having up to " << std::numeric_limits<big_int_type>::digits10 << " decimal digits\n" ;
}

buit-in integer with 64 bits of precision uses 8 bytes
and can hold numbers having up to 19 decimal digits

big integer with 1000000 bits of precision uses 125024 bytes
and can hold numbers having up to 301000 decimal digits

http://coliru.stacked-crooked.com/a/f3537fe367888e93