8000000000 choose 4000000000 fast

[fredreload]

As the title implies, I need a way to compute a huge number of permutation fast, you can test it in this calculator. The order and repetition doesn't matter so choose no for both. Now the thing is since the number is so big, it would be store inside an array of number. And I've done that much, but to computer the number requires 800000000 iteration, and it takes a long time. I saw that Python has a script call npr that can computer it really fast. I want to know if there is a way to do it for c#. In other words, I want to compute

 

8000000000! / ((4000000000!)(8000000000-4000000000)!)

 

Let me know if there is any lead in this one, I would like to know if there is a way besides 8000000000*7999999999*7999999998, etc.

 

Any help is appreciated

 

P.S. 5n 3r is 10 for the calculator, just so we have the same picture

Edited September 30, 2016 by fredreload

[fiveworlds]

A factotial is a number multiplied by the sum of the range.

[fredreload]

A factotial is a number multiplied by the sum of the range.

Cool, can you show me how to do that? I'm curious about it

[fiveworlds]

No problem.

<script>
function factorial(start) {
  temp=start;
  for (var ret = []; temp> -1; temp--) {
    ret.push(temp);
  }
  return start*ret.reduce(function(previousValue, currentValue){
    return currentValue + previousValue;
  });
}
sum = factorial(40000000);
document.write(sum);
</script>

[fredreload]

This is really cool, although I have no idea what it is doing http://stackoverflow.com/questions/18911262/parallel-calculation-of-biginteger-factorial

 

 

 

P.S. Hmm I decided to use BigInteger library for this, it is more efficient

 

No problem.

<script>
function factorial(start) {
  temp=start;
  for (var ret = []; temp> -1; temp--) {
    ret.push(temp);
  }
  return start*ret.reduce(function(previousValue, currentValue){
    return currentValue + previousValue;
  });
}
sum = factorial(40000000);
document.write(sum);
</script>

How long does it take?

Edited September 30, 2016 by fredreload

[Strange]

A factotial is a number multiplied by the sum of the range.

 

What?

 

And your code is incomprehensible, appears to be very inefficient and will run out of precision for the sort of numbers being talked about.

 

 

factorial(n) {
    if n > 1
        return n * factorial(n-1)
    else
        return 1
}

 

As far as I know, there is no shortcut for calculating this. (Although there might be techniques for evaluating the number of permutations to avoid overflowing.)

[fredreload]

I computed the dang thing Factorial(1000000) with BigInteger in like 5 minutes, but it's been 30 minutes and it hasn't printed the thing on console, why is that? By the way I am using this algorithm for compression, again, if someone is interested let me know

Edited September 30, 2016 by fredreload

[fiveworlds]

And your code is incomprehensible, appears to be very inefficient and will run out of precision for the sort of numbers being talked about.

 

 

To calculate a factorial you must

 

1. Generate the range of values for instance the range of 10 is (1,2,3,4,5,6,7,8,9,10).
2. Then the calculate the sum of that range which for 10 is 55.
3. Then multiply 55 by 10 to get the factorial.

 

So what takes a long time in the above is generating range and generating the sum of the range.

 

 

As far as I know, there is no shortcut for calculating this.

 

 

You're right there is no shortcut. However imagine we have a global cloud database. When we need to know things that are hard to generate we ask the database for the value and it is returned relatively quickly.

[fredreload]

 

 

To calculate a factorial you must

 

1. Generate the range of values for instance the range of 10 is (1,2,3,4,5,6,7,8,9,10).
2. Then the calculate the sum of that range which for 10 is 55.
3. Then multiply 55 by 10 to get the factorial.

 

So what takes a long time in the above is generating range and generating the sum of the range.

 

 

You're right there is no shortcut. However imagine we have a global cloud database. When we need to know things that are hard to generate we ask the database for the value and it is returned relatively quickly.

How do you store Factorial(1000000) in the database? I mean sure it is probably 5 million digits versus time but is the space worth it?

[Strange]

 

 

To calculate a factorial you must

 

1. Generate the range of values for instance the range of 10 is (1,2,3,4,5,6,7,8,9,10).
2. Then the calculate the sum of that range which for 10 is 55.
3. Then multiply 55 by 10 to get the factorial.

 

Even if that were the correct definition of factorial (it isn't) then you have still have a bizarrely complicated way of calculating it. To caclulate this function you have invented, it could simply be a loop:

 

for i = 1 to n {

sum = sum + i

}

result = sum * n

 

 

 

the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example,

5!=5×4×3×2×1=120. {\displaystyle 5!=5\times 4\times 3\times 2\times 1=120.\ }5! = 5 x 4 x 3 x 2 x 1 = 120

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

[ydoaPs]

What?

 

And your code is incomprehensible, appears to be very inefficient and will run out of precision for the sort of numbers being talked about.

 

 

factorial(n) {
    if n > 1
        return n * factorial(n-1)
    else
        return 1
}

As far as I know, there is no shortcut for calculating this. (Although there might be techniques for evaluating the number of permutations to avoid overflowing.)

 

Nice recursive (but not infinitely so) code. It's clear and actually does a factorial.

[Strange]

Nice recursive (but not infinitely so) code. It's clear and actually does a factorial.

 

And efficient because the compiler will (should) turn it into a simple loop.

[ydoaPs]

And efficient because the compiler will (should) turn it into a simple loop.

Not to mention that your breakout condition provides the correct answer for 0!.

[fiveworlds]

The point was that the time in calculating is lost in generating the massive list instead of just checking it against a database. This is much faster

<script>
function fact(n){
var factorial = [
"1", 
"1",
"2",
"6",
"24",
"120",
"720",
"5040",
"40320",
"362880",
"3628800",
"39916800",
"479001600",
"6227020800",
"87178291200",
"1307674368000",
"20922789888000",
"355687428096000",
"6402373705728000",
"121645100408832000",
"2432902008176640000",
"51090942171709440000",
"1124000727777607680000",
"25852016738884976640000",
"620448401733239439360000",
"15511210043330985984000000",
"403291461126605635584000000",
"10888869450418352160768000000",
"304888344611713860501504000000",
"8841761993739701954543616000000",
"265252859812191058636308480000000",
"8222838654177922817725562880000000",
"263130836933693530167218012160000000",
"8683317618811886495518194401280000000",
"295232799039604140847618609643520000000",
"10333147966386144929666651337523200000000",
"371993326789901217467999448150835200000000",
"13763753091226345046315979581580902400000000",
"523022617466601111760007224100074291200000000",
"20397882081197443358640281739902897356800000000",
"815915283247897734345611269596115894272000000000",
"33452526613163807108170062053440751665152000000000",
"1405006117752879898543142606244511569936384000000000",
"60415263063373835637355132068513997507264512000000000",
"2658271574788448768043625811014615890319638528000000000",
"119622220865480194561963161495657715064383733760000000000",
"5502622159812088949850305428800254892961651752960000000000",
"258623241511168180642964355153611979969197632389120000000000",
"12413915592536072670862289047373375038521486354677760000000000",
"608281864034267560872252163321295376887552831379210240000000000",
"30414093201713378043612608166064768844377641568960512000000000000",
"1551118753287382280224243016469303211063259720016986112000000000000",
"80658175170943878571660636856403766975289505440883277824000000000000",
"4274883284060025564298013753389399649690343788366813724672000000000000",
"230843697339241380472092742683027581083278564571807941132288000000000000",
"12696403353658275925965100847566516959580321051449436762275840000000000000",
"710998587804863451854045647463724949736497978881168458687447040000000000000",
"40526919504877216755680601905432322134980384796226602145184481280000000000000",
"2350561331282878571829474910515074683828862318181142924420699914240000000000000",
"138683118545689835737939019720389406345902876772687432540821294940160000000000000",
"8320987112741390144276341183223364380754172606361245952449277696409600000000000000",
"507580213877224798800856812176625227226004528988036003099405939480985600000000000000",
"31469973260387937525653122354950764088012280797258232192163168247821107200000000000000",
"1982608315404440064116146708361898137544773690227268628106279599612729753600000000000000",
"126886932185884164103433389335161480802865516174545192198801894375214704230400000000000000",
"8247650592082470666723170306785496252186258551345437492922123134388955774976000000000000000",
"544344939077443064003729240247842752644293064388798874532860126869671081148416000000000000000",
"36471110918188685288249859096605464427167635314049524593701628500267962436943872000000000000000",
"2480035542436830599600990418569171581047399201355367672371710738018221445712183296000000000000000",
"171122452428141311372468338881272839092270544893520369393648040923257279754140647424000000000000000",  
"11978571669969891796072783721689098736458938142546425857555362864628009582789845319680000000000000000",
"850478588567862317521167644239926010288584608120796235886430763388588680378079017697280000000000000000",
"61234458376886086861524070385274672740778091784697328983823014963978384987221689274204160000000000000000",
"4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903680000000000000000",
"330788544151938641225953028221253782145683251820934971170611926835411235700971565459250872320000000000000000",
"24809140811395398091946477116594033660926243886570122837795894512655842677572867409443815424000000000000000000",
"1885494701666050254987932260861146558230394535379329335672487982961844043495537923117729972224000000000000000000",
"145183092028285869634070784086308284983740379224208358846781574688061991349156420080065207861248000000000000000000",
"11324281178206297831457521158732046228731749579488251990048962825668835325234200766245086213177344000000000000000000",
"894618213078297528685144171539831652069808216779571907213868063227837990693501860533361810841010176000000000000000000",
"71569457046263802294811533723186532165584657342365752577109445058227039255480148842668944867280814080000000000000000000",
"5797126020747367985879734231578109105412357244731625958745865049716390179693892056256184534249745940480000000000000000000",
"475364333701284174842138206989404946643813294067993328617160934076743994734899148613007131808479167119360000000000000000000",
"39455239697206586511897471180120610571436503407643446275224357528369751562996629334879591940103770870906880000000000000000000",
"3314240134565353266999387579130131288000666286242049487118846032383059131291716864129885722968716753156177920000000000000000000",
"281710411438055027694947944226061159480056634330574206405101912752560026159795933451040286452340924018275123200000000000000000000",
"24227095383672732381765523203441259715284870552429381750838764496720162249742450276789464634901319465571660595200000000000000000000",
"2107757298379527717213600518699389595229783738061356212322972511214654115727593174080683423236414793504734471782400000000000000000000",
"185482642257398439114796845645546284380220968949399346684421580986889562184028199319100141244804501828416633516851200000000000000000000",
"16507955160908461081216919262453619309839666236496541854913520707833171034378509739399912570787600662729080382999756800000000000000000000",
"1485715964481761497309522733620825737885569961284688766942216863704985393094065876545992131370884059645617234469978112000000000000000000000",
"135200152767840296255166568759495142147586866476906677791741734597153670771559994765685283954750449427751168336768008192000000000000000000000",
"12438414054641307255475324325873553077577991715875414356840239582938137710983519518443046123837041347353107486982656753664000000000000000000000",
"1156772507081641574759205162306240436214753229576413535186142281213246807121467315215203289516844845303838996289387078090752000000000000000000000",
"108736615665674308027365285256786601004186803580182872307497374434045199869417927630229109214583415458560865651202385340530688000000000000000000000",
"10329978488239059262599702099394727095397746340117372869212250571234293987594703124871765375385424468563282236864226607350415360000000000000000000000",
"991677934870949689209571401541893801158183648651267795444376054838492222809091499987689476037000748982075094738965754305639874560000000000000000000000",
"96192759682482119853328425949563698712343813919172976158104477319333745612481875498805879175589072651261284189679678167647067832320000000000000000000000",
"9426890448883247745626185743057242473809693764078951663494238777294707070023223798882976159207729119823605850588608460429412647567360000000000000000000000",
"933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000"
];
if(factorial[n]){document.write(factorial[n]);}
else{document.write("overflowerror");}
}
fact(99);
</script>

You can easily get 9999 factorial by curling this page http://www.calculatorsoup.com/calculators/discretemathematics/factorials.php dunno if there is a better list elsewhere. You could just try doing projecteuler though... https://projecteuler.net/problem=551

 

Let's look at the practicalities of the given list when applied to standard python. Every number storable in python is already in the provided list.

 

double 1.7977e+308 factorial(171)

single 3.4028e+38 factorial(single(35))

uint64 2⁶⁴-1 factorial(uint64(21))

int64 2⁶³-1 factorial(int64(21))

uint32 2³²-1 factorial(uint32(13))

int32 2³¹-1 factorial(int32(13))

uint16 2¹⁶-1 factorial(uint16(9))

int16 2¹⁵-1 factorial(int16(8))

uint8 2⁸-1 factorial(uint8(6))

int8 2⁷-1 factorial(int8(6))

Edited September 30, 2016 by fiveworlds

[Sensei]

No problem.

<script>
function factorial(start) {
  temp=start;
  for (var ret = []; temp> -1; temp--) {
    ret.push(temp);
  }
  return start*ret.reduce(function(previousValue, currentValue){
    return currentValue + previousValue;
  });
}
sum = factorial(40000000);
document.write(sum);
</script>

 

 

Let's change your post #4 source code from initial 40000000 to say 5.

 

<script>
function factorial(start) {
temp=start;
for (var ret = []; temp> -1; temp--) {
ret.push(temp);
}
return start*ret.reduce(function(previousValue, currentValue){
return currentValue + previousValue;
});
}
sum = factorial(5);
document.write(sum);
</script>

It shows in browser "75",

but correct answer is "120" (5*4*3*2=120)

[Strange]

Every number storable in python is already in the provided list.

 

 

Nonsense.

 

I think you have posted enough erroneous crap in this thread already. Time to bow out gracefully, perhaps.

[ydoaPs]

I'm wondering how many values 5Worlds wants to hold in this list. When do we start worrying about incredible RAM usage from holding the ridiculous list affecting the speed instead of the time it takes to evaluate a for loop?

 

Also, where do we draw our arbitrary cutoff? Just go until the list is big enough to slow the computer to the point that computation is faster?

 

And why are you talking about python lists when you're not using python?

[Sensei]

How do you store Factorial(1000000) in the database? I mean sure it is probably 5 million digits versus time but is the space worth it?

In some programming situations, precalculation (lookup table) is worth doing it, if

1) calculation takes long time

2) speed of execution of code is extremely important.

3) there is no access to FPU (f.e. custom electronic chip with only integer math)

f.e. one can precalculate table with sin(angle),

and instead of using FPU trigonometric function, read sinus/cosine/tg/ctg from table.

It won't have very good precision, as angle will be integer index, instead of float.

Interpolation could slightly help, but result will be slightly slower code and having to read two (three for more advanced interpolation techniques than linear) table entries instead of one per single emulated sin/cos operation.

Table could be limited to amount of CPU cache size for optimal performance.

Edited September 30, 2016 by Sensei

[mathematic]

If you are willing to use a good approximation, Stirling's formula.

[latex]n! \approx \sqrt{2\pi n}(\frac{n}{e})^n[/latex].

 

https://en.wikipedia.org/wiki/Stirling%27s_approximation

[fredreload]

Right I saw Stirling's formula but it is only an approximation, it is fast though. Well the idea is I want to be able to compute the highest complexity, for me it would be 1GB, or 8000000000 bits. The complexity of doing a permutation on 1GB would be to choose 4000000000 bits from it for the worst case scenario. What I eventually want to get out of this is a compression formula as I have posted in the Mathmatics section. Now I was able to generate the one million bit factorial in around 30 min. I'd imagine 1000 times of that to be about 30000 minutes. So to be realistic I'd test it on 8000000 choose 4000000 which is 1MB in this case.

 

P.S. My compression algorithm goes like this:

 

1. For a 1MB file get the base permutation case on n=1 or for example 000000000000001111111111111111, store this value as 14 0's 16 1's

 

2. Compute the nth permutation for this sequence, which could be for example 110101010101010101010100111100, as long as it got 14 0's and 16 1's.

 

3. That is my data, for a 1MB file it is most likely an image.

 

4. Now my question is, I want to know where 110101010101010101010100111100 this sequence comes in as the nth permutation, we know the sequence for n=1, so I want to know which n=? is this for this sequence.

Edited October 1, 2016 by fredreload

[Strange]

P.S. My compression algorithm goes like this:

 

1. For a 1MB file get the base permutation case on n=1 or for example 000000000000001111111111111111, store this value as 14 0's 16 1's

 

2. Compute the nth permutation for this sequence, which could be for example 110101010101010101010100111100, as long as it got 14 0's and 16 1's.

 

3. That is my data, for a 1MB file it is most likely an image.

 

 

I don't see how that is supposed to work. I think you should demonstrate that the method works for smaller files before worrying about the time taken for larger ones.

[Sensei]

 

I think you should demonstrate that the method works for smaller files before worrying about the time taken for larger ones.

 

The same applies to fiveworlds (and everybody else) source codes. He should always run his code on dozen well-known values from f.e. 1... 100..

And compare result from brute-force algorithm vs his code result vs external data from net or calculator/spreadsheet.

Edited October 1, 2016 by Sensei