‹ BackHN Continuity

Thread

How big are factorials?

99 points · 43 comments · ibobev

  1. pagade · · focus · HN ↗
    Reminds me of: Professor asked us to find the biggest factorial using C programming language. And then using LISP. You can imagine our surprise.
    1. pkaye · · focus · HN ↗
      There is a algorithm call Prime Swing Factorial that can compute large factorials exactly in arbitrary precision math using prime factorization. Like 10000000! in under second depending of how optimized the math library it. Probably like 100x faster than the normal method.
      1. flcikfinder · · focus · HN ↗
        Worth noting for anyone reaching for this in practice rather than out of curiosity: several standard library implementations (Python's math.factorial is one) already use a divide-and-conquer multiplication scheme instead of naive sequential multiplication for exactly this reason, so you often get most of that speedup for free without implementing prime swing yourself.
        1. smcin · · focus · HN ↗
          (I just undead'ed this comment; can't see why it was downvoted.)
Open on Hacker News to reply ↗

Unofficial Hacker News client; not affiliated with Y Combinator.