Post Reply How to make this algorithm faster?
3088 cr points
Send Message: Send PM GB Post
30 / M
Offline
Posted 10/9/16
For other computer geeks, geniuses, scientists out there. I am currently working on a compression algorithm inspired by Silicon Valley TV series, but I'm stuck at a really slow computation speed at this for loop.

BigInteger mult = 274341;

for (int j = 1; j < 157594; j++)
{
mult *= (BigInteger)(274341 - j);
}

Having to loop 157594 times really kills the speed, so I want to discard this for loop completely if possible. Humbly asking for any opinions. Thanks for your time! And thanks Staphen for answering my previous question!
Posted 10/9/16
Can I ask why you need a massive factorial calculation in a compression algorithm?
You can try Stirling's approximation if it doesn't need to be the exact value.
37281 cr points
Send Message: Send PM GB Post
M
Offline
Posted 10/9/16 , edited 10/9/16
Who you people? Why you talk about hard maths on CR forum? Don't you know we only talk about Florida Man, and stuff that not hard?
3088 cr points
Send Message: Send PM GB Post
30 / M
Offline
Posted 10/9/16

nooneinparticular wrote:

Can I ask why you need a massive factorial calculation in a compression algorithm?
You can try Stirling's approximation if it doesn't need to be the exact value.


Stirling is only an approximation, I need it to be exact value
60151 cr points
Send Message: Send PM GB Post
27 / M
Offline
Posted 10/9/16

nooneinparticular wrote:

Can I ask why you need a massive factorial calculation in a compression algorithm?


You can see the math and a preliminary version of the algorithm in the previous thread.
http://www.crunchyroll.com/forumtopic-967951/nth-binary-permutation-for-any-binary-numbers

As for a more efficient factorial calculation, there is a pretty interesting answer here.
http://cs.stackexchange.com/questions/14456/factorial-algorithm-more-efficient-than-naive-multiplication

Though I still think your best bet is to constrain the problem and avoid factorials larger than, say, 256!.
3088 cr points
Send Message: Send PM GB Post
30 / M
Offline
Posted 10/9/16
Hmm, I just realized this is 274341! / 157594!
3088 cr points
Send Message: Send PM GB Post
30 / M
Offline
Posted 10/9/16
Here's my other thread btw http://www.scienceforums.net/topic/99210-compression-slow-but-good/
1335 cr points
Send Message: Send PM GB Post
M
Offline
Posted 10/9/16 , edited 10/9/16
You guys keep this up and I'm going to start ranting about uneven meiosis. This is too much nerdery, even for me.

Time to draft new laws.
Posted 10/9/16
Does it have to be one tiny wheel that spins 157594 times? Or, can you add more wheels, and increase the size of said wheels?

E.g. calendar leap days https://youtu.be/IJhgZBn-LHg?t=11m37s
3088 cr points
Send Message: Send PM GB Post
30 / M
Offline
Posted 10/9/16
Come on, it's a great show, feel free to talk about uneven meiosis too lol, no nerdery is going to stop you
3088 cr points
Send Message: Send PM GB Post
30 / M
Offline
Posted 10/9/16
Oh shoot, what have I done, these two forums are merging
3088 cr points
Send Message: Send PM GB Post
30 / M
Offline
Posted 10/9/16

Hrafna wrote:

Does it have to be one tiny wheel that spins 157594 times? Or, can you add more wheels, and increase the size of said wheels?

E.g. calendar leap days https://youtu.be/IJhgZBn-LHg?t=11m37s


The idea is compute multiplications fast without looping over 157594 loops, I need to get the value in O(1), I searched on Google and they suggested storing factorial value inside a database. Haven't found a better idea than this one =/
Posted 10/9/16 , edited 10/9/16


^ Me trying to understand this forum.

All I can say is... Good luck?
Posted 10/9/16 , edited 10/9/16
37281 cr points
Send Message: Send PM GB Post
M
Offline
Posted 10/10/16


Yeah... Pretty much.
You must be logged in to post.