Okey, this station is attending be rather long. I 'm attending commence with a basic job I was licking in emacs lisp. From there I 'll segue into believing about looping syntax and eventually I 'll make a little of benchmarking as I 've got the codification already and people look to wish that ( the scheme, ocaml, c++ speed comparison is out and away the most popular station on this blog followed by this
Futzing about with Undertaking Euler is something I do for fun Most recently I was looking at problem 73
- count the trimmed proper fractions with a denominator to a lesser degree or capable 10, 000 between 1/3 and 1/2.
Emacs Lisp Solution
Emacs Lisp is usually my default language for making this rather thing as I 'm already in my text editor and there is a REPL to experiment with.
Firstly, it is clear that I 'm attending postulate a mapping to compute the greatest common measure. I encountered an imperative Pa execution of Euclid 's algorithm here
A brief aside - I sought for Pa deliberately as I generally encounter it really clear. Energy anyone else make that?
(defun
gcd
(a b)
(while
(not (= b 0))
(let
((tmp b))
(setq b (% a b))
(setq a tmp)))
a)
Considering before, I 'll belike cognize what the gcd is before we name make-fraction as only fractions with a gcd of 1 will be really numerated amongst the solutions. I 've thus done gcd an optional parameter as a nod to efficiency.
(defsubst
make-fraction
(num denom &optional
gcd)
(unless
gcd (setq gcd (gcd num denom)))
(cons (/ num gcd) (/ denom gcd)))
I care the flexibleness that lisp-like languages give you to call your maps excessively.
(defsubst
more-than-1/3
(frac)
(let
((num (car frac))
(denom (cdr frac)))
(> (* num 3) denom)))
(defsubst
less-than-1/2
(frac)
(let
((num (car frac))
(denom (cdr frac)))
(< (* num 2) denom)))
(defsubst
within-range
(frac)
(and (more-than-1/3 frac) (less-than-1/2 frac)))
We but check fractions between 1/3 and 1/2 as to make all fractions with a denominator & lt; = 10, 000 would take far overly long.
(defun
solve-it
(max-denom)
(insert (format-time-string "\n\nStarted at: %H:%M:%S\n\n"
))
(let
(num denom frac max gcd solutions)
(setq solutions 0)
(setq denom 2)
(while
(<= denom max-denom)
(setq num (/ denom 3))
(setq max (1+ (/ denom 2)))
(while
(<= num max)
(setq gcd (gcd num denom))
(when
(= gcd 1)
(setq frac (make-fraction num denom gcd))
(when
(within-range frac)
;;
(insert (format "%s\n" frac))
(incf solutions)))
(incf num))
(incf denom)
(when
(= (% denom 50) 0)
(insert (format "Denom: %d Solutions: %d\n"
denom solutions)))
(sit-for 0))
(insert (format "\n%d solutions\n"
solutions))
(insert (format-time-string "Finished at: %H:%M:%S\n"
))))
After I composed this, I realised I maked n't postulate to make and destruct my fraction type so simplified to the followers:
(defun
solve-it
(max-denom)
(insert (format-time-string "\n\nStarted at: %H:%M:%S\n"
))
(let
(num denom frac max solutions)
(setq solutions 0)
(setq denom 5)
(while
(<= denom max-denom)
(setq num (1+ (/ denom 3)))
(setq max (/ denom 2))
(while
(<= num max)
(when
(= (gcd num denom) 1)
(incf solutions))
(incf num))
(incf denom))
(insert (format "%d solutions\n"
solutions))
(insert (format-time-string "Finished at: %H:%M:%S\n"
))))
(solve-it 10000)
;;
Started at: 22:14:35
;;
5066251 solutions
;;
Finished at: 22:15:45
70 seconds. Okay.
The most vexatious thing is the rude looping conceptions. while
is the basic and obvious built-in. It besides holds a heap of macros beginning with doXXX
including dotimes
and dolist
not to name the mighty common lisp loop
macro.
I make n't cognize grommet ( but I 'm attending acquire it ), but after messing some with do*
for a couple of proceedings, I realised it was n't the looping concept for me.
(do*
((i 5 (if
(> j 10) (+ i 1) i))
(j (+ i 1) (if
(> j 10) (+ i 1) (+ j 1))))
((> i 10))
(insert (format "[%d %d]"
i j)))
Yuck.
Now, the great thing about lisp is sayed to be that if you make n't care the syntax you can add your ain with macros. Unfortunately, I hold n't got about thereto yet as a cluster of people hold already projected most of the syntax I care.
Strategy Solution
When I read some of the earlier posts on this blog, it appears that strategy
holds got some nice generator syntax ( aka eager comprehensions ) for managing nested eyelets.
There are a nice set of stations on eager comprehensions here
I took print-ln
from the portable scheme station and gcd
from SICP
#lang scheme/base
(require srfi/42)
(define
(print-ln
. args)
(for-each
display args)
(newline)
(flush-output))
(define
(gcd
a b)
(if
(= b 0) a
(gcd b (remainder a b))))
(define
(solve-it
max-denom)
(sum-ec (:range
denom 2 (+ max-denom 1))
(:range
num (+ (floor (/ denom 3)) 1) (ceiling (/ denom 2)))
(if
(= (gcd num denom) 1) 1 0)))
(print-ln "There are "
(solve-it 10000) " solutions"
)
Yikes, mzscheme is much speedier than emacs-lisp. That surprised ME A factor of 10 I would hold anticipated, a factor of 50 not suchly.
$ time mzscheme frac.scm
There are XXX solutions
real 0m1.413s
user 0m1.404s
sys 0m0.004s
Perl Solution
use
strict
;
use
warnings
;
use
POSIX
qw
(floor ceil)
;
sub
gcd
{
my
($n1
, $n2
) = @_
;
until
($n2 == 0) {
my
$tmp
= $n2;
$n2 = $n1 % $n2;
$n1 = $tmp;
}
return
$n1;
}
The nested eyelet really looks OK to me in perl although not equally nice as the srfi-42 eager comprehensions.
sub
solve_it
{
my
$max_denom
= $_
[0];
my
$solutions
= 0;
foreach
my
$denom
(5..$max_denom) {
my
$max
= ceil($denom / 2) - 1;
foreach
my
$num
((1 + floor($denom / 3))..$max) {
if
(gcd($num, $denom) == 1) {
++$solutions;
}
}
}
return
$solutions;
}
printf
"There are
%d
solutions\n"
, solve_it(10000);
The performance of my perl is jollily bad overly.
$ time perl frac.pl
There are XXX solutions
real 0m47.026s
user 0m46.963s
sys 0m0.008s
Ocaml Solution
let
rec
gcd
a b
=
if
b =
0 then
a
else
gcd b (
a mod
b);;
let
solve_it
max_denom
=
let
rec
loop
num denom solutions
=
if
denom >
max_denom then
solutions
else
if
num >=
(
denom/
2+
1)
then
loop ((
denom+
1)/
3+
1)
(
denom+
1)
solutions
else
begin
if
gcd num denom =
1 then
begin
(* Printf.printf "%d/%d\n" num denom; *)
loop (
num+
1)
denom (
solutions+
1)
end
else
loop (
num+
1)
denom solutions
end
in
loop ((
5/
3)+
1)
5 0;;
Printf
.printf "There are %d solutions\n"
(
solve_it 1000);;
Oh love, I appear to hold an atrocious accent when programming ocaml. I 'll take to work on it.
$ time ./a.out
There are XXX solutions
real 0m1.071s
user 0m1.060s
sys 0m0.004s
So, Decisions
For this particular labor ( looping and integer maths ) Emacs Lisp is slow, but not that retard compared with another scripting language. I really care the strategy looping conceptions and mzscheme is surprisingly speedy ( again, only for this diminutive thing ), not overly far from the ocaml - although again I should underline that the ocaml is a direful drudge. And eventually, I take to acquire how to utilize loop
properly.
All inputs welcome.
![[info]](http://l-stat.livejournal.com/img/userinfo.gif){kind=small}
