Clojure Golf – Episode 2: Largest Prime Factor

[Fogus]

;; largest prime factor
(defn lpf
"Takes a number n and a starting number d > 1
and calculates the largest prime factor of n
starting at number d.

usage: (lpf 364362978 2) => 8675309"
[n d]
(if (> d n)
(- d 1)
(recur
(#(if (zero? (rem % d))
(recur (/ % d))
%)
n)
(inc d))))

This is the smallest `lpf` that I could come up with -- can you do
better? Can you make it faster (shouldn't be too hard, considering
mine is atrociously slow)?

More information at: http://blog.fogus.me/2009/09/09/clojure-golf-episode-2-largest-prime-factor/

Have at it!

-m

[eyeris]

Why did you define the problem as you did rather than simply "The
largest prime factor of n?"

> More information at:http://blog.fogus.me/2009/09/09/clojure-golf-episode-2-largest-prime-...
>
> Have at it!
>
> -m

[Timothy Pratley]

> (zero? (rem % d))
(= 0 (rem % d))

>     (- d 1)
presumably you chose this instead of (dec d) because it converts one
real character into whitespace

so if you make this:
>      (inc d))))
(+ d 1)
You can convert another whitespace! [arguably its a meaningful
whitespace but lets ignore that for now]

Oh and you could call your function l instead of lpf :)
Ok so I don't have any useful suggestion sorry... but interesting to
read your post, That recur inside a lambda was cute!

[MarkSwanson]

I took a stab at it. I used:
(set! *warn-on-reflection* true)
but it didn't tell me anything.

I found a Java class that did the same thing and created a Clojure
implementation from that. I thought that perhaps if I could force the
data types to be BigInteger Clojure would save time by not having to
use reflection.

However, this fails and I'm not sure why. The code:

(defn lpf3 [#^bigint arg]
(print (str "The prime factorization of " arg " is :"))
(println (loop [i (bigint 2) n (bigint arg) ]
;(println (str "i:" i "n:" n))
(if (<= i (/ n i))
(recur (inc i) (loop [n2 (bigint n)]
;(println (str "n2:" n2))
(if (zero? (rem n2 i))
(recur (/ n2 i) )
n2 )))
n)))
)

The error:
The prime factorization of 234 is :#<CompilerException
java.lang.ClassCastException: java.lang.Integer cannot be cast to
java.math.BigInteger (REPL:17)>
NOTE: Line 17 in this case looks like "n2 )))"

I tried to create a version using long to see if that would help. It
did as I received better compiler error messages. The end result:
(too many casts perhaps...)
(defn lpf6 [arg]
(print (str "The prime factorization of " arg " is :"))
(println (loop [i (long 2) n (long arg) ]
(if (<= i (/ n i))
(recur (long (inc i)) (long (loop [n2 (long n)]
(if (zero? (rem n2 i))
(recur (long (/ n2 i)) )
n2 ))))
(long n))))
)

Clojure=> (time (lpf6 364362978))
The prime factorization of 364362978 is :8675309
"Elapsed time: 133.974784 msecs"

Your code on the same machine gives:
Clojure=> (time (lpf 364362978 2))
"Elapsed time: 1014.572527 msecs"
8675309

I suspect casting to long would speed things up a bit in your case.
However, long doesn't have enough precision to handle the number you
mentioned in your article:
1234567890123456789012345678901234567890

The correct solution would be to coerce the types to bigint. I've done
this and the results are interesting. Strangely bigint is over 10x
faster than long:

Clojure=> (time (lpf6b 364362978))
The prime factorization of 364362978 is :8675309
"Elapsed time: 8.874452 msecs"

The code:

(defn lpf6b [arg]
(print (str "The prime factorization of " arg " is :"))
(println (loop [i (bigint 2) n (bigint arg) ]
(if (<= i (/ n i))
(recur (bigint (inc i)) (bigint (loop [n2 (bigint n)]
(if (zero? (rem n2 i))
(recur (bigint (/ n2 i)) )
n2 ))))
(bigint n))))
)

I can only guess that bigint is faster here because I was not casting
long correctly in enough (or in the correct) places and was actually
causing the compiler more work. If this is obvious to anyone please
post. I'm intrigued.

My next stab would have been in GLSL with Clojure Penumbra. Purely for
fun :-) But I'm out of time.

Cheers.

[MarkSwanson]

Just for fun I actually tried this:

Clojure=> (time (lpf6b 1234567890123456789012345678901234567890))
The prime factorization of 1234567890123456789012345678901234567890
is :5964848081
"Elapsed time: 5519.278432 msecs"

I can't confirm the answer is correct.
5.5 seconds sure beats 10 minutes. :-)

[Christophe Grand]

I propose to compute the score of a golf competition entry using this function:
(defn score [expr] (count (tree-seq coll? #(if (map? %) (apply concat
%) (seq %)) expr)))

Thus, shorter names and literal anonymous closures won't change the score.

--
Professional: http://cgrand.net/ (fr)
On Clojure: http://clj-me.blogspot.com/ (en)

[Adrian Cuthbertson]

What about a golf competition on the golf competition scorer? Then we
can evaluate that using;
(defmacro score-scorer [scorer] ... )
:)

- Adrian

[Mark Reid]

Hi,

Just thought you would like to know that Wolfram|Alpha agrees (in
roughly the same time):

http://www.wolframalpha.com/input/?i=factor+1234567890123456789012345678901234567890

Regards,

Mark.
--
http://mark.reid.name

[MarkSwanson]

> Just thought you would like to know that Wolfram|Alpha agrees (in
> roughly the same time):
>

> http://www.wolframalpha.com/input/?i=factor+1234567890123456789012345...

Thanks!