prog

frontpage - thread list - new thread - preferences - ?

[challenge] Inverse Factorial

1 2021-06-03 11:09

Write a program that takes an integer m as input and returns the integer n such that n! = m. It should accept m with up to one million digits and print an error message if m isn't the factorial of a non-negative integer.

2 2021-06-03 11:57

Meh.

(defun infac (n)
  (loop for i from 0
	for f = (fac i)
	when (> f n) do (error "Not a factorial")
	when (= f n) return i))

3 2021-06-03 12:52

>>2
How long to compute (infac (fact 1000000)) ?

4 2021-06-03 17:51 *

(define (inverse-factorial n)
  (letrec ((iter
            (lambda (i a)
              (cond
               ((> a n) (error "Not a factorial!"))
               ((= a n) (- i 1))
               (else (iter (+ i 1) (* a i)))))))
    (iter 1 1)))

5 2021-06-03 18:14 *

>>4
How long to compute (inverse-factorial (factorial 1000000)) ?

6 2021-06-03 19:10

#lang racket ;;; v7.9
(require math/special-functions)
(require math/base)
(define (fact n) (gamma (+ 1 n)))
(define (invfact n)
  (define w (log n))
  (define c (/ (log (* 2 pi)) -2))
  (define (¡ xₙ)
    (let ((xₙ₊₁ (improve xₙ)))
      (if (< (abs (- xₙ xₙ₊₁)) 0.001)
          (check (exact-round xₙ₊₁))
          (¡ xₙ₊₁))))
  (define (improve x) (- (/ (+ x w c) (log x)) 0.5))
  (define (check res)
    (if (= n (fact res))
        res
        "not a factorial"))
  (if (< n 3)
      n
      (¡ 10)))

~~a few seconds~~

7 2021-06-03 19:23

>>5
It is linear in time if we ignore that bignum operations. Wikipedia says that the best known multiplication algorithm is O(n log(n)), therefore theoretically it could be O(n² log(n)), but it will depend on your Scheme implementation.

What are some cases where 1000000! is interesting? I thought 70! was already well over the number of observable particles in the universe, why would you need to compute and reverse it?

8 2021-06-03 19:50

>>7
I believe it's absolutely useless but I don't see a problem there.

9 2021-06-03 20:26

>>2
Finite time.

10 2021-06-04 06:18

>>6
and invfact(fact(10000000)) takes 20+20 seconds! Is this Newton's iterative method?

11 2021-06-04 07:19 *

>>10
Yes. It converges very quickly.

12 2021-06-06 22:13

Remember that

n! = 1 * 2 * ... * (n - 2) * (n - 1) * n

Then starting with 2 one should go up until m is factored, otherwise it's not a factorial.
This method is O(n) or O(sqrt(m)), but I'm not sure if there are better way to do this.

13 2021-06-06 22:58 *

>>12
If the remainder from division is not 0 it returns earlier.
This method like >>2,4 fails miserably if m is a very large factorial like fact(1000000).

14 2021-06-07 17:11

>>13
As long as it gives you the right result in finite time, it hasn't failed.

15 2021-06-08 17:48

>>13
Undeniable proof that it actually does work for any positive integer: https://paste.textboard.org/3df10a35

16 2021-06-09 10:41 *

>>15
How do you prove the proof contains no flaws?

17 2021-06-09 11:36 *

>>16
Type checking!

18 2021-06-09 18:55

>>15-17
The real question is always: did we actually prove what we wanted to prove? Embarrassingly the paste only proves that the inverse of n! is n. But, for example, it says nothing about the inverse of n!-1 which could also be n. Here's an extended version that also proves that if the inverse of m is n, then m must be n!: https://paste.textboard.org/399b89fa

19 2021-06-09 22:54

>>18 That's the trick with theorems and automated tests and such.
You're trying to approach the thing from multiple angles.
In math maybe you start with a conjecture that's something explicit then you come around with an implicit proof.
Software is the same.

20 2021-08-13 04:13

For later.

>>> import operator
>>> import functools
>>> f = lambda n: len (str (functools.reduce (operator.mul, range (1, n + 1))))
>>> f (205021)
999994
>>> f (205022)
1000000

21 2021-08-17 17:38 *

>>20
Stop adding spaces before opening parentheses.

22