Hello
Recently, I was trying the problems at the UVa website. As is the case with
many, my first problem was the 3n+1 problem. After solving it I found that the
best solution for the problem had a runtime of 0.000 seconds. That solution was
in C++. I was wondering if fast programs like that are possible in Lisp. If you
think it is, I request you to share your code with me. I also welcome guidance
in this regard.
Regards,
Cross
On Apr 17, 5:51 am, Cross <····@X.tv> wrote:
> I was wondering if fast programs like that are possible in Lisp. If you
> think it is, I request you to share your code with me. I also welcome guidance
> in this regard.
Of course the distinct possibity exists that you're just trolling for
homework answers. If so, who am I to dissuade you from wasting your
tuition dollars by not actually learning. If not, and this is a
legitimate request for common lisp code:
(defun cycle-length (n &optional (counter 0))
(declare (optimize (speed 3) (safety 0) (debug 0))
(fixnum n counter))
(incf counter)
(cond ((= n 1) (return-from cycle-length counter))
((oddp n) (cycle-length (1+ (* 3 n)) counter))
(t (cycle-length (/ n 2) counter))))
(defun process-tuple (first-num second-num)
(declare (optimize (speed 3) (safety 0) (debug 0))
(fixnum first-num second-num))
(let* ((max (loop for x from first-num to second-num
maximizing (cycle-length x))))
(format t "~a ~a ~a ~%" first-num second-num max)))
(defun run-sample ()
(let* ((sample (list 1 10 100 200 201 210 900 1000)))
(loop for (first-num second-num) on sample by #'cddr do
(process-tuple first-num second-num))))
#|
? (time (run-sample))
1 10 20
100 200 125
201 210 89
900 1000 174
(RUN-SAMPLE) took 0 milliseconds (0.000 seconds) to run
with 2 available CPU cores.
|#
On Apr 17, 10:10 am, Raffael Cavallaro <················@gmail.com>
wrote:
> On Apr 17, 5:51 am, Cross <····@X.tv> wrote:
>
> > I was wondering if fast programs like that are possible in Lisp. If you
> > think it is, I request you to share your code with me. I also welcome guidance
> > in this regard.
>
> Of course the distinct possibity exists that you're just trolling for
> homework answers. If so, who am I to dissuade you from wasting your
> tuition dollars by not actually learning. If not, and this is a
> legitimate request for common lisp code:
>
> (defun cycle-length (n &optional (counter 0))
> (declare (optimize (speed 3) (safety 0) (debug 0))
> (fixnum n counter))
> (incf counter)
> (cond ((= n1) (return-from cycle-length counter))
> ((oddp n) (cycle-length (1+ (* 3 n)) counter))
> (t (cycle-length (/ n 2) counter))))
>
> (defun process-tuple (first-num second-num)
> (declare (optimize (speed 3) (safety 0) (debug 0))
> (fixnum first-num second-num))
> (let* ((max (loop for x from first-num to second-num
> maximizing (cycle-length x))))
> (format t "~a ~a ~a ~%" first-num second-num max)))
>
> (defun run-sample ()
> (let* ((sample (list110 100 200 201 210 900 1000)))
> (loop for (first-num second-num) on sample by #'cddr do
> (process-tuple first-num second-num))))
>
> #|
> ? (time (run-sample))110 20
> 100 200 125
> 201 210 89
> 900 1000 174
> (RUN-SAMPLE) took 0 milliseconds (0.000 seconds) to run
> with 2 available CPU cores.
>
> |#
I have seen mention of bit-shifting in C. Can one do it in lisp?
In clisp, I came up with the following code to do the (3n+1)/2 (since
3n+1 is even, we could immediately divide by two) using byte
operations. The code below uses binary ops to calculate 2n+1, then
adds n to get 3n+1 (as in the wikipedia article on that problem
http://en.wikipedia.org/wiki/Collatz_conjecture) and finally divides
by two by shifting right by one.
(let ((a 5)
(b 0))
;; shift to left by one (equivalent to multiply by 2)
(setf (ldb (byte 5 1) b) (ldb (byte 5 0) a))
;; add one
(setf (ldb (byte 1 0) b) 1)
;; add n and return all bits but last one
(ldb (byte 5 1) (+ b a)))
Now this could be much fixed and improved
- my byte operations operate on an arbitrary width 5 - I am not sure
how to relate the width to the integers a&b
- I'm also lost regarding declaring a&b as integers of some fixed
size (or not patient enough to read hyperspec and clisp documentation)
- finally the last addition (+ b a) might be shortened. We know that
the last bits of b & a are unity, so we do not need to add them, just
carry over 1 to the addition of the next least significant bits of a &
b
With this last comment, the (ldb (byte 5 1) (+ b a))) form in the
code above is replaced by
(+ (ldb (byte 5 1) b)
(ldb (byte 5 1) a)
1))
Does all that improve the speed? Don't know yet. If someone helps me
improve the declarative parts of the code and the byte length
specification, we may get an answer.
Cheers,
Mirko
Mirko <·············@gmail.com> writes:
> I have seen mention of bit-shifting in C. Can one do it in lisp?
>
> In clisp, I came up with the following code to do the (3n+1)/2 (since
> 3n+1 is even, we could immediately divide by two) using byte
> operations. The code below uses binary ops to calculate 2n+1, then
> adds n to get 3n+1 (as in the wikipedia article on that problem
> http://en.wikipedia.org/wiki/Collatz_conjecture) and finally divides
> by two by shifting right by one.
>
> (let ((a 5)
> (b 0))
> ;; shift to left by one (equivalent to multiply by 2)
> (setf (ldb (byte 5 1) b) (ldb (byte 5 0) a))
Why should you take only 5 bits?
(defun hotpo (n)
(if (oddp n)
(+ (ash n 1) n 1) ; 3n+1
(ash n -1)) ; n/2
--
__Pascal Bourguignon__
On Apr 19, 8:15 pm, ····@informatimago.com (Pascal J. Bourguignon)
wrote:
> Mirko <·············@gmail.com> writes:
> > I have seen mention of bit-shifting in C. Can one do it in lisp?
>
> > In clisp, I came up with the following code to do the (3n+1)/2 (since
> > 3n+1 is even, we could immediately divide by two) using byte
> > operations. The code below uses binary ops to calculate 2n+1, then
> > adds n to get 3n+1 (as in the wikipedia article on that problem
> >http://en.wikipedia.org/wiki/Collatz_conjecture) and finally divides
> > by two by shifting right by one.
>
> > (let ((a 5)
> > (b 0))
> > ;; shift to left by one (equivalent to multiply by 2)
> > (setf (ldb (byte 5 1) b) (ldb (byte 5 0) a))
>
> Why should you take only 5 bits?
>
> (defun hotpo (n)
> (if (oddp n)
> (+ (ash n 1) n 1) ; 3n+1
> (ash n -1)) ; n/2
>
> --
> __Pascal Bourguignon__
1) I was doing 5 bits because I could not figure out how many bits
were in a,b (or even lamer, how to declare them), so I picked 5 to
play around with
2) ash -- cool, did not know about it.
3) thank you :-)
(I get this nagging suspicion that Mr. Bourguignon is the name of a
secret organization consisting of many people around the globe since
he/it/they seems to post very quickly)
Mirko wrote:
> On Apr 19, 8:15 pm, ····@informatimago.com (Pascal J. Bourguignon)
> wrote:
>> Mirko <·············@gmail.com> writes:
>>> I have seen mention of bit-shifting in C. Can one do it in lisp?
>>> In clisp, I came up with the following code to do the (3n+1)/2 (since
>>> 3n+1 is even, we could immediately divide by two) using byte
>>> operations. The code below uses binary ops to calculate 2n+1, then
>>> adds n to get 3n+1 (as in the wikipedia article on that problem
>>> http://en.wikipedia.org/wiki/Collatz_conjecture) and finally divides
>>> by two by shifting right by one.
>>> (let ((a 5)
>>> (b 0))
>>> ;; shift to left by one (equivalent to multiply by 2)
>>> (setf (ldb (byte 5 1) b) (ldb (byte 5 0) a))
>> Why should you take only 5 bits?
>>
>> (defun hotpo (n)
>> (if (oddp n)
>> (+ (ash n 1) n 1) ; 3n+1
>> (ash n -1)) ; n/2
>>
>> --
>> __Pascal Bourguignon__
>
> 1) I was doing 5 bits because I could not figure out how many bits
> were in a,b (or even lamer, how to declare them), so I picked 5 to
> play around with
> 2) ash -- cool, did not know about it.
> 3) thank you :-)
>
> (I get this nagging suspicion that Mr. Bourguignon is the name of a
> secret organization consisting of many people around the globe since
> he/it/they seems to post very quickly)
I long suspected that too. :) Probably people from the suspicious Lug
organization...
>> (I get this nagging suspicion that Mr. Bourguignon is the name of a
>> secret organization consisting of many people around the globe since
>> he/it/they seems to post very quickly)
>
> I long suspected that too. :) Probably people from the suspicious Lug
> organization...
Ha! He's also well trained in other disciplines too - like Objective-C
and Cocoa! (Oh man, Cocotron under CCL Windows - that would be nice!)
I do admire him for his broad and at the same time deep knowledge!
On Apr 20, 5:31 pm, "Dimiter \"malkia\" Stanev" <······@mac.com>
wrote:
> >> (I get this nagging suspicion that Mr. Bourguignon is the name of a
> >> secret organization consisting of many people around the globe since
> >> he/it/they seems to post very quickly)
>
> > I long suspected that too. :) Probably people from the suspicious Lug
> > organization...
>
> Ha! He's also well trained in other disciplines too - like Objective-C
> and Cocoa! (Oh man, Cocotron under CCL Windows - that would be nice!)
>
> I do admire him for his broad and at the same time deep knowledge!
Ney, impossible. It just proves that these posts are a front for some
shadowy organization (come to think of it aren't all lispers in the
shadow of C, Python, and horrors, Ruby?)
Um, actually, I will lay off for fairness sake. Thanks Pascal, again.
Cross <·@X.tv> writes:
> Hello
>
> Recently, I was trying the problems at the UVa website. As is the case with
> many, my first problem was the 3n+1 problem. After solving it I found that the
> best solution for the problem had a runtime of 0.000 seconds. That solution was
> in C++. I was wondering if fast programs like that are possible in Lisp. If you
> think it is, I request you to share your code with me. I also welcome guidance
> in this regard.
With what input did you have a runtime of 0.000 seconds?
--
(espen)
+ Cross <·@X.tv>:
> Recently, I was trying the problems at the UVa website. As is the case
> with many, my first problem was the 3n+1 problem. After solving it I
> found that the best solution for the problem had a runtime of 0.000
> seconds.
Fascinating. And I thought the problem was still unsolved.
--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- It is undesirable to believe a proposition
when there is no ground whatsoever for supposing it is true.
-- Bertrand Russell
On Apr 17, 8:06 am, Harald Hanche-Olsen <······@math.ntnu.no> wrote:
> + Cross <····@X.tv>:
>
> > Recently, I was trying the problems at the UVa website. As is the case
> > with many, my first problem was the 3n+1 problem. After solving it I
> > found that the best solution for the problem had a runtime of 0.000
> > seconds.
>
> Fascinating. And I thought the problem was still unsolved.
Ahh. He's referring to the ACM contest problems. The problem
is the first one. It's used to help new users get adjusted
to the judging environment.
http://icpcres.ecs.baylor.edu/onlinejudge/external/1/100.pdf
--
Geoff
Harald Hanche-Olsen wrote:
> + Cross <·@X.tv>:
>
>> Recently, I was trying the problems at the UVa website. As is the case
>> with many, my first problem was the 3n+1 problem. After solving it I
>> found that the best solution for the problem had a runtime of 0.000
>> seconds.
>
> Fascinating. And I thought the problem was still unsolved.
>
I apologise for the confusion. My solution was not the ace solution. My solution
is at 0.067 seconds.
The input set is from 1 to 100000.
On Apr 17, 1:06 pm, Cross <····@X.tv> wrote:
> Harald Hanche-Olsen wrote:
> > + Cross <····@X.tv>:
>
> >> Recently, I was trying the problems at the UVa website. As is the case
> >> with many, my first problem was the 3n+1 problem. After solving it I
> >> found that the best solution for the problem had a runtime of 0.000
> >> seconds.
>
> > Fascinating. And I thought the problem was still unsolved.
>
> I apologise for the confusion. My solution was not the ace solution. My solution
> is at 0.067 seconds.
>
> The input set is from 1 to 100000.
the pdf that Geoff S. links to says the inputs will be "less than
10,000 and greater than 0." Are you sure you mean 100,000?
Raffael Cavallaro wrote:
> On Apr 17, 1:06 pm, Cross <····@X.tv> wrote:
>> Harald Hanche-Olsen wrote:
>>> + Cross <····@X.tv>:
>>>> Recently, I was trying the problems at the UVa website. As is the case
>>>> with many, my first problem was the 3n+1 problem. After solving it I
>>>> found that the best solution for the problem had a runtime of 0.000
>>>> seconds.
>>> Fascinating. And I thought the problem was still unsolved.
>> I apologise for the confusion. My solution was not the ace solution. My solution
>> is at 0.067 seconds.
>>
>> The input set is from 1 to 100000.
>
> the pdf that Geoff S. links to says the inputs will be "less than
> 10,000 and greater than 0." Are you sure you mean 100,000?
The UVa site is temporarily unavailable so I shall provide the link when it is
available. Please remind me. My exam pressure made way for an error, its not
100,000, it is 1,000,000.
Here is the question as I got it.
Problems in Computer Science are often classified as belonging to a certain
class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be
analyzing a property of an algorithm whose classification is not known for all
possible inputs.
The Problem
Consider the following algorithm:
1. input n
2. print n
3. if n = 1 then STOP
4. if n is odd then n<-3n+1
5. else n<-n/2
6. GOTO 2
Given the input 22, the following sequence of numbers will be printed 22 11 34
17 52 26 13 40 20 10 5 16 8 4 2 1
It is conjectured that the algorithm above will terminate (when a 1 is printed)
for any integral input value. Despite the simplicity of the algorithm, it is
unknown whether this conjecture is true. It has been verified, however, for all
integers n such that 0 < n < 1,000,000 (and, in fact, for many more numbers than
this.)
Given an input n, it is possible to determine the number of numbers printed
(including the 1). For a given n this is called the cycle-length of n. In the
example above, the cycle length of 22 is 16.
For any two numbers i and j you are to determine the maximum cycle length over
all numbers between i and j.
The Input
The input will consist of a series of pairs of integers i and j, one pair of
integers per line. All integers will be less than 1,000,000 and greater than 0.
You should process all pairs of integers and for each pair determine the maximum
cycle length over all integers between and including i and j.
You can assume that no operation overflows a 32-bit integer.
The Output
For each pair of input integers i and j you should output i, j, and the maximum
cycle length for integers between and including i and j. These three numbers
should be separated by at least one space with all three numbers on one line and
with one line of output for each line of input. The integers i and j must appear
in the output in the same order in which they appeared in the input and should
be followed by the maximum cycle length (on the same line).
Sample Input
1 10
100 200
201 210
900 1000
Sample Output
1 10 20
100 200 125
201 210 89
900 1000 174
Cross escreveu:
> Raffael Cavallaro wrote:
>> On Apr 17, 1:06 pm, Cross <····@X.tv> wrote:
>>> Harald Hanche-Olsen wrote:
>>>> + Cross <····@X.tv>:
>>>>> Recently, I was trying the problems at the UVa website. As is the case
>>>>> with many, my first problem was the 3n+1 problem. After solving it I
>>>>> found that the best solution for the problem had a runtime of 0.000
>>>>> seconds.
>>>> Fascinating. And I thought the problem was still unsolved.
>>> I apologise for the confusion. My solution was not the ace solution. My solution
>>> is at 0.067 seconds.
>>>
>>> The input set is from 1 to 100000.
>> the pdf that Geoff S. links to says the inputs will be "less than
>> 10,000 and greater than 0." Are you sure you mean 100,000?
> The UVa site is temporarily unavailable so I shall provide the link when it is
> available. Please remind me. My exam pressure made way for an error, its not
> 100,000, it is 1,000,000.
Hmm, from 1 to 1,000,000 it takes Larceny Scheme 5.491 secs and Python
takes 31.533 secs on a Core 2 Duo. It really takes only 0.0067 secs in
C++? Would you share that code with us? What machine are you running
it in?
--
a game sig: http://tinyurl.com/d3rxz9
namekuseijin wrote:
> Cross escreveu:
>> Raffael Cavallaro wrote:
>>> On Apr 17, 1:06 pm, Cross <····@X.tv> wrote:
>>>> Harald Hanche-Olsen wrote:
>>>>> + Cross <····@X.tv>:
>>>>>> Recently, I was trying the problems at the UVa website. As is the
>>>>>> case
>>>>>> with many, my first problem was the 3n+1 problem. After solving it I
>>>>>> found that the best solution for the problem had a runtime of 0.000
>>>>>> seconds.
>>>>> Fascinating. And I thought the problem was still unsolved.
>>>> I apologise for the confusion. My solution was not the ace solution.
>>>> My solution
>>>> is at 0.067 seconds.
>>>>
>>>> The input set is from 1 to 100000.
>>> the pdf that Geoff S. links to says the inputs will be "less than
>>> 10,000 and greater than 0." Are you sure you mean 100,000?
>> The UVa site is temporarily unavailable so I shall provide the link
>> when it is
>> available. Please remind me. My exam pressure made way for an error,
>> its not
>> 100,000, it is 1,000,000.
>
> Hmm, from 1 to 1,000,000 it takes Larceny Scheme 5.491 secs and Python
> takes 31.533 secs on a Core 2 Duo. It really takes only 0.0067 secs in
> C++? Would you share that code with us? What machine are you running
> it in?
>
I worked it in C. Here is my code.
#include <stdio.h>
unsigned int cycles(register unsigned int n){
if(n&1){
if(n==1)return 1;
else{
n+=(n+1)>>1;
return cycles(n)+2;
/*the next one will obviously be odd, so we can add two cycles and skip a
funtion call*/
}
}else
return cycles(n>>1)+1;
}
int main(){
unsigned int i, j;
register unsigned int max, r, t;
int c;
while((c=getchar())!=EOF){
ungetc(c, stdin);
scanf("%u%u\n", &i, &j);
max=0;
if(i<j){
t=i;
do{
if((r=cycles(t++))>max)max=r;
}while(t<=j);
}else{
t=j;
do{
if((r=cycles(t++))>max)max=r;
}while(t<=i);
}
printf("%u %u %u\n", i, j, max);
}
return 0;
}
The time was measured on the server. It was compiled on gcc. The allowed
optimizations were -O2 -pipe.
Cross escreveu:
> namekuseijin wrote:
>> Cross escreveu:
>>> Raffael Cavallaro wrote:
>>>> On Apr 17, 1:06 pm, Cross <····@X.tv> wrote:
>>>>> Harald Hanche-Olsen wrote:
>>>>>> + Cross <····@X.tv>:
>>>>>>> Recently, I was trying the problems at the UVa website. As is the
>>>>>>> case
>>>>>>> with many, my first problem was the 3n+1 problem. After solving it I
>>>>>>> found that the best solution for the problem had a runtime of 0.000
>>>>>>> seconds.
>>>>>> Fascinating. And I thought the problem was still unsolved.
>>>>> I apologise for the confusion. My solution was not the ace solution.
>>>>> My solution
>>>>> is at 0.067 seconds.
>>>>>
>>>>> The input set is from 1 to 100000.
>>>> the pdf that Geoff S. links to says the inputs will be "less than
>>>> 10,000 and greater than 0." Are you sure you mean 100,000?
>>> The UVa site is temporarily unavailable so I shall provide the link
>>> when it is
>>> available. Please remind me. My exam pressure made way for an error,
>>> its not
>>> 100,000, it is 1,000,000.
>> Hmm, from 1 to 1,000,000 it takes Larceny Scheme 5.491 secs and Python
>> takes 31.533 secs on a Core 2 Duo. It really takes only 0.0067 secs in
>> C++? Would you share that code with us? What machine are you running
>> it in?
>>
>
> I worked it in C. Here is my code.
> #include <stdio.h>
> unsigned int cycles(register unsigned int n){
> if(n&1){
> if(n==1)return 1;
> else{
> n+=(n+1)>>1;
> return cycles(n)+2;
> /*the next one will obviously be odd, so we can add two cycles and skip a
> funtion call*/
> }
> }else
> return cycles(n>>1)+1;
> }
> int main(){
> unsigned int i, j;
> register unsigned int max, r, t;
> int c;
>
> while((c=getchar())!=EOF){
> ungetc(c, stdin);
> scanf("%u%u\n", &i, &j);
> max=0;
> if(i<j){
> t=i;
> do{
> if((r=cycles(t++))>max)max=r;
> }while(t<=j);
> }else{
> t=j;
> do{
> if((r=cycles(t++))>max)max=r;
> }while(t<=i);
> }
> printf("%u %u %u\n", i, j, max);
> }
> return 0;
> }
>
> The time was measured on the server. It was compiled on gcc. The allowed
> optimizations were -O2 -pipe.
and you fed it a file with a single line:
1 1000000
is that right?
Clever low-level machinery with register variables, bit shifting and
other fun...
--
a game sig: http://tinyurl.com/d3rxz9
> and you fed it a file with a single line:
> 1 1000000
>
> is that right?
>
Well I had tried that in a single line; can't say about the UVa server. I have a
core 2 duo 1.73 Ghz 1 GB ram system.
Cross escreveu:
> I apologise for the confusion. My solution was not the ace solution. My solution
> is at 0.067 seconds.
>
> The input set is from 1 to 100000.
In Scheme:
; http://icpcres.ecs.baylor.edu/onlinejudge/external/1/100.pdf
(define (cycle-length n)
(do ((i n (if (odd? i) (+ 1 (* 3 i)) (/ i 2)))
(length 1 (+ 1 length)))
((= i 1) length)))
(define (max-cycle-length from to)
(do ((n from (+ 1 n))
(r 1 (max r (cycle-length n))))
((> n to) r)))
Timings in one native-compiled implementation and one jit-compiled:
Larceny v0.97b1 (beta test) (Aug 25 2008 10:57:44, precise:Win32:unified)
larceny.heap, built on Mon 08/25/2008
> (load "uva-3n_plus_1-max-cycle-length.scm")
> (time (max-cycle-length 1 100000))
Words allocated: 0
Words reclaimed: 0
Elapsed time...: 468 ms (User: 468 ms; System: 0 ms)
Elapsed GC time: 0 ms (CPU: 0 in 0 collections.)
351
Welcome to MzScheme v4.0.2 [3m], Copyright (c) 2004-2008 PLT Scheme Inc.
> (load "uva-3n_plus_1-max-cycle-length.scm")
> (time (max-cycle-length 1 100000))
cpu time: 1014 real time: 1014 gc time: 0
351
> (time (max-cycle-length 1 100000))
cpu time: 983 real time: 982 gc time: 0
351
I don't have Gambit, Bigloo or Stalin available right now, so getting
down to C++ speed is difficult. I'm curious about your C++
implementation though...
--
a game sig: http://tinyurl.com/d3rxz9
On Apr 17, 1:51 pm, namekuseijin <············@gmail.com> wrote:
> Cross escreveu:
>
> > I apologise for the confusion. My solution was not the ace solution. My solution
> > is at 0.067 seconds.
>
> > The input set is from 1 to 100000.
>
> In Scheme:
>
> ;http://icpcres.ecs.baylor.edu/onlinejudge/external/1/100.pdf
>
> (define (cycle-length n)
> (do ((i n (if (odd? i) (+ 1 (* 3 i)) (/ i 2)))
> (length 1 (+ 1 length)))
> ((= i 1) length)))
>
> (define (max-cycle-length from to)
> (do ((n from (+ 1 n))
> (r 1 (max r (cycle-length n))))
> ((> n to) r)))
>
> Timings in one native-compiled implementation and one jit-compiled:
>
> Larceny v0.97b1 (beta test) (Aug 25 2008 10:57:44, precise:Win32:unified)
> larceny.heap, built on Mon 08/25/2008
>
> > (load "uva-3n_plus_1-max-cycle-length.scm")
>
> > (time (max-cycle-length 1 100000))
> Words allocated: 0
> Words reclaimed: 0
> Elapsed time...: 468 ms (User: 468 ms; System: 0 ms)
> Elapsed GC time: 0 ms (CPU: 0 in 0 collections.)
> 351
>
> Welcome to MzScheme v4.0.2 [3m], Copyright (c) 2004-2008 PLT Scheme Inc.
> > (load "uva-3n_plus_1-max-cycle-length.scm")
> > (time (max-cycle-length 1 100000))
> cpu time: 1014 real time: 1014 gc time: 0
> 351
> > (time (max-cycle-length 1 100000))
> cpu time: 983 real time: 982 gc time: 0
> 351
>
> I don't have Gambit, Bigloo or Stalin available right now, so getting
> down to C++ speed is difficult. I'm curious about your C++
> implementation though...
>
> --
> a game sig:http://tinyurl.com/d3rxz9
using your version (suitably translated to common lisp as necessary)
and the same inputs (1 100000) I get these timings for various scheme
and lisp implementations:
CCL: 0.334 seconds
LispWorks: 0.59 seconds
sbcl: 0.363 seconds
gambit: 2.626 seconds
mzscheme (jit): 1.9 seconds
larceny: 0.513
On 17 Apr, 23:21, Raffael Cavallaro <················@gmail.com>
wrote:
> using your version (suitably translated to common lisp as necessary)
> and the same inputs (1 100000) I get these timings for various scheme
> and lisp implementations:
>
> CCL: 0.334 seconds
> LispWorks: 0.59 seconds
It's easy to get the LW timings dramatically down by using the fixnum-
safety declaration:
(defun 3n+1-cycle-length (n)
(declare (optimize (safety 0)(fixnum-safety 0))
(fixnum n))
(loop for count from 1
when (= n 1)
return count
do
(if (oddp n)
(setf n (+ (* 3 n) 1))
(setf n (/ n 2)))))
(defun 3n+1-max-cycle-length (from to)
(declare (optimize (safety 0)(fixnum-safety 0))
(fixnum from to))
(loop for i from from to to
maximize (3n+1-cycle-length i)))
;; Testing:
CL-USER 36 > (time (3n+1-max-cycle-length 1 100000))
Timing the evaluation of (3N+1-MAX-CYCLE-LENGTH 1 100000)
User time = 0.043
System time = 0.000
Elapsed time = 0.045
Allocation = 0 bytes
0 Page faults
351
CL-USER 37 >
(Test environment: 2.8GHz Core 2 Duo MacBook Pro running 64 bit LW for
mac)
On Apr 17, 6:43 pm, ·····@vestre.net wrote:
> On 17 Apr, 23:21, Raffael Cavallaro <················@gmail.com>
> wrote:
>
> > using your version (suitably translated to common lisp as necessary)
> > and the same inputs (1 100000) I get these timings for various scheme
> > and lisp implementations:
>
> > CCL: 0.334 seconds
> > LispWorks: 0.59 seconds
>
> It's easy to get the LW timings dramatically down by using the fixnum-
> safety declaration:
>
> (defun 3n+1-cycle-length (n)
> (declare (optimize (safety 0)(fixnum-safety 0))
> (fixnum n))
> (loop for count from 1
> when (= n 1)
> return count
> do
> (if (oddp n)
> (setf n (+ (* 3 n) 1))
> (setf n (/ n 2)))))
>
> (defun 3n+1-max-cycle-length (from to)
> (declare (optimize (safety 0)(fixnum-safety 0))
> (fixnum from to))
> (loop for i from from to to
> maximize (3n+1-cycle-length i)))
>
> ;; Testing:
>
> CL-USER 36 > (time (3n+1-max-cycle-length 1 100000))
> Timing the evaluation of (3N+1-MAX-CYCLE-LENGTH 1 100000)
>
> User time = 0.043
> System time = 0.000
> Elapsed time = 0.045
> Allocation = 0 bytes
> 0 Page faults
> 351
>
> CL-USER 37 >
>
> (Test environment: 2.8GHz Core 2 Duo MacBook Pro running 64 bit LW for
> mac)
I tried (declare (fixnum-safety 0)) in my first set of timings, but it
caused lispworks to lock up so I redid the timing without that
declaration. This is LWM 5.1.2 32-bit intel.
On 18 Apr, 00:48, Raffael Cavallaro <················@gmail.com>
wrote:
> On Apr 17, 6:43 pm, ·····@vestre.net wrote:
>
>
>
> > On 17 Apr, 23:21, Raffael Cavallaro <················@gmail.com>
> > wrote:
>
> > > using your version (suitably translated to common lisp as necessary)
> > > and the same inputs (1 100000) I get these timings for various scheme
> > > and lisp implementations:
>
> > > CCL: 0.334 seconds
> > > LispWorks: 0.59 seconds
>
> > It's easy to get the LW timings dramatically down by using the fixnum-
> > safety declaration:
>
> > (defun 3n+1-cycle-length (n)
> > (declare (optimize (safety 0)(fixnum-safety 0))
> > (fixnum n))
> > (loop for count from 1
> > when (= n 1)
> > return count
> > do
> > (if (oddp n)
> > (setf n (+ (* 3 n) 1))
> > (setf n (/ n 2)))))
>
> > (defun 3n+1-max-cycle-length (from to)
> > (declare (optimize (safety 0)(fixnum-safety 0))
> > (fixnum from to))
> > (loop for i from from to to
> > maximize (3n+1-cycle-length i)))
>
> > ;; Testing:
>
> > CL-USER 36 > (time (3n+1-max-cycle-length 1 100000))
> > Timing the evaluation of (3N+1-MAX-CYCLE-LENGTH 1 100000)
>
> > User time = 0.043
> > System time = 0.000
> > Elapsed time = 0.045
> > Allocation = 0 bytes
> > 0 Page faults
> > 351
>
> > CL-USER 37 >
>
> > (Test environment: 2.8GHz Core 2 Duo MacBook Pro running 64 bit LW for
> > mac)
>
> I tried (declare (fixnum-safety 0)) in my first set of timings, but it
> caused lispworks to lock up so I redid the timing without that
> declaration. This is LWM 5.1.2 32-bit intel.
Interesting, same thing happened to me right now (I also tried it in
LWM 5.1.2 32-bit intel).
Anyway, the 64 bit version happily chews away on any input, e.g.:
CL-USER 40 > (time (3n+1-max-cycle-length 1 100000000))
Timing the evaluation of (3N+1-MAX-CYCLE-LENGTH 1 100000000)
User time = 0:01:12.784
System time = 3.412
Elapsed time = 0:01:18.613
Allocation = 104 bytes
2 Page faults
950
On 18 Apr, 00:59, ·····@vestre.net wrote:
> Interesting, same thing happened to me right now (I also tried it in
> LWM 5.1.2 32-bit intel).
Not very strange, though: one of the sequences contains 1570824736,
which is not a fixnum in the 32 bit version.
On Apr 17, 7:19 pm, ·····@vestre.net wrote:
> On 18 Apr, 00:59, ·····@vestre.net wrote:
>
> > Interesting, same thing happened to me right now (I also tried it in
> > LWM 5.1.2 32-bit intel).
>
> Not very strange, though: one of the sequences contains 1570824736,
> which is not a fixnum in the 32 bit version.
I thought we might be running into most-positive-fixnum territory.
·····@vestre.net writes:
>
> (defun 3n+1-cycle-length (n)
> (declare (optimize (safety 0)(fixnum-safety 0))
> (fixnum n))
> (loop for count from 1
> when (= n 1)
> return count
> do
> (if (oddp n)
> (setf n (+ (* 3 n) 1))
> (setf n (/ n 2)))))
>
> (defun 3n+1-max-cycle-length (from to)
> (declare (optimize (safety 0)(fixnum-safety 0))
> (fixnum from to))
> (loop for i from from to to
> maximize (3n+1-cycle-length i)))
Hmmm. Does adding type declarations for the loop variables improve
things any? This is, BTW, a more general comment for all of the
LOOP-based solutions in this thread.
(loop for count FIXNUM from 1 ...)
(loop for i FIXNUM from from to to ...)
--
Thomas A. Russ, USC/Information Sciences Institute
···@sevak.isi.edu (Thomas A. Russ) writes:
> Hmmm. Does adding type declarations for the loop variables improve
> things any? This is, BTW, a more general comment for all of the
> LOOP-based solutions in this thread.
No, it won't for my LW version, the (fixnum-safety 0) declaration will
make the compiler assume everything is fixnum anyway.
I'm not good at reading assembly, but this looks pretty "bare bones" to
me:
CL-USER 1 > (disassemble '3n+1-cycle-length)
4010023BB4:
0: 41BA08000000 move r10d, 8
L1: 6: 4883FF08 cmpq rdi, 8
10: 7509 jne L2
12: 4C89D7 moveq rdi, r10
15: B901000000 move ecx, 1
20: C3 ret
L2: 21: 40F6C708 testb dil, 8
25: 750A jne L4
27: 48C1FF01 sarq rdi, 1
L3: 31: 4983C208 addq r10, 8
35: EBE1 jmp L1
L4: 37: 486BFF03 imulq rdi, rdi, 3
41: 4883C708 addq rdi, 8
45: EBF0 jmp L3
47: 004100 addb [rcx], al
50: 0000 addb [rax], al
NIL
--
(espen)
On Apr 21, 8:32 am, Espen Vestre <·····@vestre.net> wrote:
> And btw. I think the whole competition is rather boring. It's much more
> fun to play with math stuff using bignums anyway, especially for
> problems like this one. For instance, the sequence length divided by the
> number of bits in the number appears to approach 7-something for large
> numbers. Now if I only could find a theorem proving something like that
> ;-)
<http://en.wikipedia.org/wiki/Collatz_conjecture>
i.e., unlikely, since it's unproven that the sequence even terminates
for all inputs, but I suspect you already knew that...
Raffael Cavallaro <················@gmail.com> writes:
>> And btw. I think the whole competition is rather boring. It's much more
>> fun to play with math stuff using bignums anyway, especially for
>> problems like this one. For instance, the sequence length divided by the
>> number of bits in the number appears to approach 7-something for large
>> numbers. Now if I only could find a theorem proving something like that
>> ;-)
>
> <http://en.wikipedia.org/wiki/Collatz_conjecture>
>
> i.e., unlikely, since it's unproven that the sequence even terminates
> for all inputs, but I suspect you already knew that...
Sure, I know it's unproven.
I just wanted to show how much more fun it is to play with an unlimited
implementation here. It's kind of sad to compete implementing the
fastest solution for small numbers, since that's a useless toy program,
while a fast solution for bignums could actually be usable as a tool for
a mathematician working on this problem.
Btw. a reader, who thought it was too off-topic, wrote me and gave a
nice little mathematical outline of why the 7.something number shows up
for randomly chosen big numbers.
I also had a look at the upper bound of the sequence length/bit length
fraction for some intervals, and it stays in the 28-32 range even for
large numbers, e.g. the largest fraction in between 1.03 million and
1.04 million is 28.3. This corresponds nicely with the obvious
observation one can make from the scatterplots on the Wikipedia page:
That the upper bound looks a lot like a logarithmic function :-)
--
(espen)
* Espen Vestre <··············@vestre.net>
Wrote on Tue, 21 Apr 2009 20:52:12 +0200:
| I just wanted to show how much more fun it is to play with an unlimited
| implementation here. It's kind of sad to compete implementing the
| fastest solution for small numbers, since that's a useless toy program,
| while a fast solution for bignums could actually be usable as a tool for
| a mathematician working on this problem.
|
| Btw. a reader, who thought it was too off-topic, wrote me and gave a
| nice little mathematical outline of why the 7.something number shows up
| for randomly chosen big numbers.
I followed up to the thread without seeing this article. Would it be
possible to send me the outline, or share it on usenet ?
| I also had a look at the upper bound of the sequence length/bit length
| fraction for some intervals, and it stays in the 28-32 range even for
| large numbers, e.g. the largest fraction in between 1.03 million and
| 1.04 million is 28.3. This corresponds nicely with the obvious
| observation one can make from the scatterplots on the Wikipedia page:
| That the upper bound looks a lot like a logarithmic function :-)
--
Madhu
Madhu <·······@meer.net> writes:
> | Btw. a reader, who thought it was too off-topic, wrote me and gave a
> | nice little mathematical outline of why the 7.something number shows up
> | for randomly chosen big numbers.
>
> I followed up to the thread without seeing this article. Would it be
> possible to send me the outline, or share it on usenet ?
I'll leave it to the guy who sent me this to decide if he wants to share
it with you too. But just to be sure that everyone has grasped this by
now: Be aware that while it seems that most numbers cluster around this
value, of course there will always outliers, i.e. 2^n, which has a
sequence length of n+1, and thus a sequence length to bit length
fraction of about 1, and the upper outliers that seem to very rarely go
beyond a fraction of 30, but where it is unknown whether there may exist
infinite sequences.
Anyway, I haven't really worked on this problem at all, and left
academia and mathematics for programming 15 years ago, so don't trust
me.
All I'm saying is that implementing 32- or 64-bit arithmetic functions
for this kind of number-theoretic problems suddenly seemed utterly
useless to me.
--
(espen)
Espen Vestre wrote:
> Madhu <·······@meer.net> writes:
>
>> | Btw. a reader, who thought it was too off-topic, wrote me and gave a
>> | nice little mathematical outline of why the 7.something number shows up
>> | for randomly chosen big numbers.
>>
>> I followed up to the thread without seeing this article. Would it be
>> possible to send me the outline, or share it on usenet ?
>
> I'll leave it to the guy who sent me this to decide if he wants to share
> it with you too. But just to be sure that everyone has grasped this by
> now: Be aware that while it seems that most numbers cluster around this
> value, of course there will always outliers, i.e. 2^n, which has a
> sequence length of n+1, and thus a sequence length to bit length
> fraction of about 1, and the upper outliers that seem to very rarely go
> beyond a fraction of 30, but where it is unknown whether there may exist
> infinite sequences.
>
> Anyway, I haven't really worked on this problem at all, and left
> academia and mathematics for programming 15 years ago, so don't trust
> me.
>
> All I'm saying is that implementing 32- or 64-bit arithmetic functions
> for this kind of number-theoretic problems suddenly seemed utterly
> useless to me.
I hope he does.
Espen Vestre <·····@vestre.net> writes:
>
> And btw. I think the whole competition is rather boring. It's much more
> fun to play with math stuff using bignums anyway, especially for
> problems like this one. For instance, the sequence length divided by the
> number of bits in the number appears to approach 7-something for large
> numbers. Now if I only could find a theorem proving something like that
> ;-)
This is off topic, but because some people have shown interest, here it is.
What about the following reasoning, this is no proof at all, but
just some thoughts on why this constant shows up.
Let A(n) be the sequence length of n. Now of course there are two
cases:
n is even: A(n)= A(n/2) + 1
n is odd: A(n) = A(1.5n+0.5) + 2 [3n+1 is even, so divide by two]
Now lets assume that the chance of an odd number after one of these
steps is 0.5 and the chance of an even number is also 0.5.
In addition, lets simplify the relation A(n) = A(1.5n + 0.5) + 2 to
A(n)=A(1.5n) + 2.
So we are left with:
A(n) = A(n/2) + 1 in half of the cases
A(n) = A(1.5n) + 2 in half of the cases.
This gives the recursion formula:
A(n) = 0.5 * ( A(n/2) + 1) + 0.5 * ( A(1.5n) + 2)
If we rewrite this a bit and replace m = 1.5n we get:
A(m) = 2 A(2/3 * m) - A (m/3) - 3
Now this recurrance has a solution of the form:
A(m) = a log (m)
Substituting this solution gives:
a * log(m) = 2 * a * (log (m) + log (2/3))
- a * (log (m) + log (1/3))
- 3
Simplifying the above gives:
0 = a * (2 * log (2/3) - log (1/3)) - 3
or in other words:
a = 3 / (2 * log (2/3) - log (1/3))
= 3 / (2 log (2) - log (3))
a ~ 10.42817849034662
so
A(m) ~ 10.42817849034662 * log (m)
Of course this is in the natural log. If we rewrite this into the base
2 log we get:
A(m) ~ 7.228262518959627 * log2(m)
and because log2(m) is the number of bits in m this heuristic gives
that:
Sequence length of m is roughly 7.228262518959627 times the number of bits
in m.
Kind regards,
Wim Oudshoorn.
Willem Rein Oudshoorn wrote:
>
> This is off topic, but because some people have shown interest, here it is.
>
> What about the following reasoning, this is no proof at all, but
> just some thoughts on why this constant shows up.
>
> Let A(n) be the sequence length of n. Now of course there are two
> cases:
>
> n is even: A(n)= A(n/2) + 1
> n is odd: A(n) = A(1.5n+0.5) + 2 [3n+1 is even, so divide by two]
>
> Now lets assume that the chance of an odd number after one of these
> steps is 0.5 and the chance of an even number is also 0.5.
> In addition, lets simplify the relation A(n) = A(1.5n + 0.5) + 2 to
> A(n)=A(1.5n) + 2.
>
> So we are left with:
>
> A(n) = A(n/2) + 1 in half of the cases
> A(n) = A(1.5n) + 2 in half of the cases.
>
> This gives the recursion formula:
>
> A(n) = 0.5 * ( A(n/2) + 1) + 0.5 * ( A(1.5n) + 2)
>
> If we rewrite this a bit and replace m = 1.5n we get:
>
> A(m) = 2 A(2/3 * m) - A (m/3) - 3
>
> Now this recurrance has a solution of the form:
>
> A(m) = a log (m)
>
> Substituting this solution gives:
>
> a * log(m) = 2 * a * (log (m) + log (2/3))
> - a * (log (m) + log (1/3))
> - 3
>
> Simplifying the above gives:
>
> 0 = a * (2 * log (2/3) - log (1/3)) - 3
>
> or in other words:
>
> a = 3 / (2 * log (2/3) - log (1/3))
> = 3 / (2 log (2) - log (3))
>
> a ~ 10.42817849034662
>
> so
> A(m) ~ 10.42817849034662 * log (m)
>
> Of course this is in the natural log. If we rewrite this into the base
> 2 log we get:
>
> A(m) ~ 7.228262518959627 * log2(m)
>
> and because log2(m) is the number of bits in m this heuristic gives
> that:
>
> Sequence length of m is roughly 7.228262518959627 times the number of bits
> in m.
>
> Kind regards,
>
> Wim Oudshoorn.
Thank you for it with us.
* Willem Rein Oudshoorn <··············@Silver.oudshoorn.nl> :
Wrote on Wed, 22 Apr 2009 16:27:19 +0200:
| This is off topic, but because some people have shown interest, here
| it is.
|
| What about the following reasoning, this is no proof at all, but
| just some thoughts on why this constant shows up.
|
| Let A(n) be the sequence length of n. Now of course there are two
| cases:
[...]
| A(m) ~ 7.228262518959627 * log2(m)
|
| and because log2(m) is the number of bits in m this heuristic gives
| that:
|
| Sequence length of m is roughly 7.228262518959627 times the number of
| bits in m.
Thanks a lot for posting this.
[I'm not a mathematician at all but I was able to follow most of it, and
think it is pretty neat
If I understand it right, the crucial assumptions on which this hinges
are 1) that repetition of numbers in the sequence and the possible
existence of cycles for large n will not impact the result of the
analysis, and 2) odd and even numbers at any step of the sequence are
equally likely. (Both assumptions seem OK to me)]
Appreciate your sharing this!
--
Madhu
Madhu ha escrito:
> * Willem Rein Oudshoorn <··············@Silver.oudshoorn.nl> :
> Wrote on Wed, 22 Apr 2009 16:27:19 +0200:
>
> | This is off topic, but because some people have shown interest, here
> | it is.
> |
> | What about the following reasoning, this is no proof at all, but
> | just some thoughts on why this constant shows up.
> |
> | Let A(n) be the sequence length of n. Now of course there are two
> | cases:
>
> [...]
>
> | A(m) ~ 7.228262518959627 * log2(m)
> |
> | and because log2(m) is the number of bits in m this heuristic gives
> | that:
> |
> | Sequence length of m is roughly 7.228262518959627 times the number of
> | bits in m.
>
> Thanks a lot for posting this.
>
> [I'm not a mathematician at all but I was able to follow most of it, and
> think it is pretty neat
>
> If I understand it right, the crucial assumptions on which this hinges
> are 1) that repetition of numbers in the sequence and the possible
> existence of cycles for large n will not impact the result of the
> analysis, and 2) odd and even numbers at any step of the sequence are
> equally likely. (Both assumptions seem OK to me)]
>
> Appreciate your sharing this!
> --
> Madhu
Another intuitive way without recurrence relations, using the
geometric mean.
with probability 1/2 you do x -> x/2 and with probability 1/2 you do
x -> x*3/2, so
you can think that on the average (geometric mean) in one "step" you
do
x-> x*k with k the geometric mean, that is sqrt(1/2*3/2).
So we obtain:
sqrt(1.5*0.5) = 0.86602540378444
log(2.0^m)/log(0.866)*3/2 = -7.226788725203257*m
Here we multiply by 3/2 because the 3/2 factor is two step 3*1/2, so
the typical
1/2 * 3/2 is composed of 1/2 * 3 * 1/2 , that is 2 steps are 3 steps.
camposdeviento wrote:
> Madhu ha escrito:
>> * Willem Rein Oudshoorn <··············@Silver.oudshoorn.nl> :
>> Wrote on Wed, 22 Apr 2009 16:27:19 +0200:
>>
>> | This is off topic, but because some people have shown interest, here
>> | it is.
>> |
>> | What about the following reasoning, this is no proof at all, but
>> | just some thoughts on why this constant shows up.
>> |
>> | Let A(n) be the sequence length of n. Now of course there are two
>> | cases:
>>
>> [...]
>>
>> | A(m) ~ 7.228262518959627 * log2(m)
>> |
>> | and because log2(m) is the number of bits in m this heuristic gives
>> | that:
>> |
>> | Sequence length of m is roughly 7.228262518959627 times the number of
>> | bits in m.
>>
>> Thanks a lot for posting this.
>>
>> [I'm not a mathematician at all but I was able to follow most of it, and
>> think it is pretty neat
>>
>> If I understand it right, the crucial assumptions on which this hinges
>> are 1) that repetition of numbers in the sequence and the possible
>> existence of cycles for large n will not impact the result of the
>> analysis, and 2) odd and even numbers at any step of the sequence are
>> equally likely. (Both assumptions seem OK to me)]
>>
>> Appreciate your sharing this!
>> --
>> Madhu
>
>
> Another intuitive way without recurrence relations, using the
> geometric mean.
>
> with probability 1/2 you do x -> x/2 and with probability 1/2 you do
> x -> x*3/2, so
> you can think that on the average (geometric mean) in one "step" you
> do
> x-> x*k with k the geometric mean, that is sqrt(1/2*3/2).
>
> So we obtain:
>
> sqrt(1.5*0.5) = 0.86602540378444
>
> log(2.0^m)/log(0.866)*3/2 = -7.226788725203257*m
>
> Here we multiply by 3/2 because the 3/2 factor is two step 3*1/2, so
> the typical
> 1/2 * 3/2 is composed of 1/2 * 3 * 1/2 , that is 2 steps are 3 steps.
>
>
>
I am happy to have created this thread. Now, I understand why Graham believes
that Lisp makes you a better programmer for the rest of your life.
Madhu <·······@meer.net> wrote:
+---------------
| Willem Rein Oudshoorn <··············@Silver.oudshoorn.nl> :
| | A(m) ~ 7.228262518959627 * log2(m)
...
| | bits in m.
...
|
| If I understand it right, the crucial assumptions on which this hinges
| are 1) that repetition of numbers in the sequence and the possible
| existence of cycles for large n will not impact the result of the
| analysis, and 2) odd and even numbers at any step of the sequence are
| equally likely. (Both assumptions seem OK to me)]
+---------------
In the original formulation of the problem, Assumption #2 was *definitely*
incorrect, since (a) odd numbers can *only* be followed by even numbers,
and (b) even numbers can be followed by up to log2(n) even numbers.
What I haven't worked through yet is whether this strong bias towards
even numbers in the original problem follows through into Oudshoorn's
reformulation...
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
* Raffael Cavallaro
Wrote on Tue, 21 Apr 2009 11:20:22 -0700 (PDT):
| On Apr 21, 8:32 am, Espen Vestre <·····@vestre.net> wrote:
|
|> And btw. I think the whole competition is rather boring. It's much more
|> fun to play with math stuff using bignums anyway, especially for
|> problems like this one. For instance, the sequence length divided by the
|> number of bits in the number appears to approach 7-something for large
|> numbers. Now if I only could find a theorem proving something like that
|> ;-)
|
| <http://en.wikipedia.org/wiki/Collatz_conjecture>
|
| i.e., unlikely, since it's unproven that the sequence even terminates
| for all inputs, but I suspect you already knew that...
I think Espen Vestre was implicitly implying that if the property he
discovered could be proved, then there would be a new way to solve the
open problem.
Even if Espen's property could be shown to true for sequences that
terminate, it would open up a new (possibly IT based) approach for
solving the open problem. (So far I've not seen this approach taken in
the tiny amount of literature I've seen)
--
Madhu
Raffael Cavallaro escreveu:
> On Apr 17, 1:51 pm, namekuseijin <············@gmail.com> wrote:
>> Cross escreveu:
>>
>>> I apologise for the confusion. My solution was not the ace solution. My solution
>>> is at 0.067 seconds.
>>> The input set is from 1 to 100000.
>> In Scheme:
>>
>> ;http://icpcres.ecs.baylor.edu/onlinejudge/external/1/100.pdf
>>
>> (define (cycle-length n)
>> (do ((i n (if (odd? i) (+ 1 (* 3 i)) (/ i 2)))
>> (length 1 (+ 1 length)))
>> ((= i 1) length)))
>>
>> (define (max-cycle-length from to)
>> (do ((n from (+ 1 n))
>> (r 1 (max r (cycle-length n))))
>> ((> n to) r)))
>>
>> Timings in one native-compiled implementation and one jit-compiled:
>>
>> Larceny v0.97b1 (beta test) (Aug 25 2008 10:57:44, precise:Win32:unified)
>> larceny.heap, built on Mon 08/25/2008
>>
>> > (load "uva-3n_plus_1-max-cycle-length.scm")
>>
>> > (time (max-cycle-length 1 100000))
>> Words allocated: 0
>> Words reclaimed: 0
>> Elapsed time...: 468 ms (User: 468 ms; System: 0 ms)
>> Elapsed GC time: 0 ms (CPU: 0 in 0 collections.)
>> 351
>>
>> Welcome to MzScheme v4.0.2 [3m], Copyright (c) 2004-2008 PLT Scheme Inc.
>> > (load "uva-3n_plus_1-max-cycle-length.scm")
>> > (time (max-cycle-length 1 100000))
>> cpu time: 1014 real time: 1014 gc time: 0
>> 351
>> > (time (max-cycle-length 1 100000))
>> cpu time: 983 real time: 982 gc time: 0
>> 351
>>
>> I don't have Gambit, Bigloo or Stalin available right now, so getting
>> down to C++ speed is difficult. I'm curious about your C++
>> implementation though...
>>
>> --
>> a game sig:http://tinyurl.com/d3rxz9
>
> using your version (suitably translated to common lisp as necessary)
> and the same inputs (1 100000) I get these timings for various scheme
> and lisp implementations:
>
> CCL: 0.334 seconds
> LispWorks: 0.59 seconds
> sbcl: 0.363 seconds
> gambit: 2.626 seconds
> mzscheme (jit): 1.9 seconds
> larceny: 0.513
gambit compiles to quite performant C code. The gsi interpreter that
comes with it is slow.
--
a game sig: http://tinyurl.com/d3rxz9
On Apr 17, 5:33 pm, namekuseijin <············@gmail.com> wrote:
> Raffael Cavallaro escreveu:
>
>
>
>
>
> > On Apr 17, 1:51 pm, namekuseijin <············@gmail.com> wrote:
> >> Cross escreveu:
>
> >>> I apologise for the confusion. My solution was not the ace solution. My solution
> >>> is at 0.067 seconds.
> >>> The input set is from 1 to 100000.
> >> In Scheme:
>
> >> ;http://icpcres.ecs.baylor.edu/onlinejudge/external/1/100.pdf
>
> >> (define (cycle-length n)
> >> (do ((i n (if (odd? i) (+ 1 (* 3 i)) (/ i 2)))
> >> (length 1 (+ 1 length)))
> >> ((= i 1) length)))
>
> >> (define (max-cycle-length from to)
> >> (do ((n from (+ 1 n))
> >> (r 1 (max r (cycle-length n))))
> >> ((> n to) r)))
>
> >> Timings in one native-compiled implementation and one jit-compiled:
>
> >> Larceny v0.97b1 (beta test) (Aug 25 2008 10:57:44, precise:Win32:unified)
> >> larceny.heap, built on Mon 08/25/2008
>
> >> > (load "uva-3n_plus_1-max-cycle-length.scm")
>
> >> > (time (max-cycle-length 1 100000))
> >> Words allocated: 0
> >> Words reclaimed: 0
> >> Elapsed time...: 468 ms (User: 468 ms; System: 0 ms)
> >> Elapsed GC time: 0 ms (CPU: 0 in 0 collections.)
> >> 351
>
> >> Welcome to MzScheme v4.0.2 [3m], Copyright (c) 2004-2008 PLT Scheme Inc.
> >> > (load "uva-3n_plus_1-max-cycle-length.scm")
> >> > (time (max-cycle-length 1 100000))
> >> cpu time: 1014 real time: 1014 gc time: 0
> >> 351
> >> > (time (max-cycle-length 1 100000))
> >> cpu time: 983 real time: 982 gc time: 0
> >> 351
>
> >> I don't have Gambit, Bigloo or Stalin available right now, so getting
> >> down to C++ speed is difficult. I'm curious about your C++
> >> implementation though...
>
> >> --
> >> a game sig:http://tinyurl.com/d3rxz9
>
> > using your version (suitably translated to common lisp as necessary)
> > and the same inputs (1 100000) I get these timings for various scheme
> > and lisp implementations:
>
> > CCL: 0.334 seconds
> > LispWorks: 0.59 seconds
> > sbcl: 0.363 seconds
> > gambit: 2.626 seconds
> > mzscheme (jit): 1.9 seconds
> > larceny: 0.513
>
> gambit compiles to quite performant C code. The gsi interpreter that
> comes with it is slow.
>
> --
> a game sig:http://tinyurl.com/d3rxz9
this was compiled with gsc's compile-file
Raffael Cavallaro escreveu:
>>> CCL: 0.334 seconds
>>> LispWorks: 0.59 seconds
>>> sbcl: 0.363 seconds
>>> gambit: 2.626 seconds
>>> mzscheme (jit): 1.9 seconds
>>> larceny: 0.513
>> gambit compiles to quite performant C code. The gsi interpreter that
>> comes with it is slow.
>>
>> --
>> a game sig:http://tinyurl.com/d3rxz9
>
> this was compiled with gsc's compile-file
holy crap!
--
a game sig: http://tinyurl.com/d3rxz9
Raffael Cavallaro wrote:
> On Apr 17, 1:51�pm, namekuseijin <············@gmail.com> wrote:
> > Cross escreveu:
> >
> > > I apologise for the confusion. My solution was not the ace
> > > solution. My solution �is at 0.067 seconds.
> >
> > > The input set is from 1 to 100000.
> >
> > In Scheme:
> >
> > ;http://icpcres.ecs.baylor.edu/onlinejudge/external/1/100.pdf
> >
> > (define (cycle-length n)
> > � �(do ((i n (if (odd? i) (+ 1 (* 3 i)) (/ i 2)))
> > � � � � (length 1 (+ 1 length)))
> > � � �((= i 1) length)))
> >
> > (define (max-cycle-length from to)
> > � �(do ((n from (+ 1 n))
> > � � � � (r 1 (max r (cycle-length n))))
> > � � �((> n to) r)))
> >
> > Timings in one native-compiled implementation and one jit-compiled:
> >
> > Larceny v0.97b1 (beta test) (Aug 25 2008 10:57:44,
> > precise:Win32:unified) larceny.heap, built on Mon 08/25/2008
> >
> > �> (load "uva-3n_plus_1-max-cycle-length.scm")
> >
> > �> (time (max-cycle-length 1 100000))
> > Words allocated: 0
> > Words reclaimed: 0
> > Elapsed time...: 468 ms (User: 468 ms; System: 0 ms)
> > Elapsed GC time: 0 ms (CPU: 0 in 0 collections.)
> > 351
> >
> > Welcome to MzScheme v4.0.2 [3m], Copyright (c) 2004-2008 PLT Scheme
> > Inc. �> (load "uva-3n_plus_1-max-cycle-length.scm")
> > �> (time (max-cycle-length 1 100000))
> > cpu time: 1014 real time: 1014 gc time: 0
> > 351
> > �> (time (max-cycle-length 1 100000))
> > cpu time: 983 real time: 982 gc time: 0
> > 351
> >
> > I don't have Gambit, Bigloo or Stalin available right now, so
> > getting down to C++ speed is difficult. �I'm curious about your C++
> > implementation though...
> >
> > --
> > a game sig:http://tinyurl.com/d3rxz9
>
> using your version (suitably translated to common lisp as necessary)
> and the same inputs (1 100000) I get these timings for various scheme
> and lisp implementations:
>
> CCL: 0.334 seconds
> LispWorks: 0.59 seconds
> sbcl: 0.363 seconds
> gambit: 2.626 seconds
> mzscheme (jit): 1.9 seconds
> larceny: 0.513
OCaml: 0.161 seconds (on 2GHz laptop)
let cycle_length n =
let rec loop n length =
if n > 1 then
loop ( if n land 1 > 0 then 3*n + 1 else n / 2 ) (succ length)
else length
in loop n 1 ;;
let max_cycle_length low high =
let m = ref 0 in
for n = low to high do
m := max !m (cycle_length n)
done ;
!m ;;
On Apr 18, 2:51 am, "William James" <·········@yahoo.com> wrote:
> Raffael Cavallaro wrote:
> > On Apr 17, 1:51 pm, namekuseijin <············@gmail.com> wrote:
> > > Cross escreveu:
>
> > > > I apologise for the confusion. My solution was not the ace
> > > > solution. My solution is at 0.067 seconds.
>
> > > > The input set is from 1 to 100000.
>
> > > In Scheme:
>
> > > ;http://icpcres.ecs.baylor.edu/onlinejudge/external/1/100.pdf
>
> > > (define (cycle-length n)
> > > (do ((i n (if (odd? i) (+ 1 (* 3 i)) (/ i 2)))
> > > (length 1 (+ 1 length)))
> > > ((= i 1) length)))
>
> > > (define (max-cycle-length from to)
> > > (do ((n from (+ 1 n))
> > > (r 1 (max r (cycle-length n))))
> > > ((> n to) r)))
>
> > > Timings in one native-compiled implementation and one jit-compiled:
>
> > > Larceny v0.97b1 (beta test) (Aug 25 2008 10:57:44,
> > > precise:Win32:unified) larceny.heap, built on Mon 08/25/2008
>
> > > > (load "uva-3n_plus_1-max-cycle-length.scm")
>
> > > > (time (max-cycle-length 1 100000))
> > > Words allocated: 0
> > > Words reclaimed: 0
> > > Elapsed time...: 468 ms (User: 468 ms; System: 0 ms)
> > > Elapsed GC time: 0 ms (CPU: 0 in 0 collections.)
> > > 351
>
> > > Welcome to MzScheme v4.0.2 [3m], Copyright (c) 2004-2008 PLT Scheme
> > > Inc. > (load "uva-3n_plus_1-max-cycle-length.scm")
> > > > (time (max-cycle-length 1 100000))
> > > cpu time: 1014 real time: 1014 gc time: 0
> > > 351
> > > > (time (max-cycle-length 1 100000))
> > > cpu time: 983 real time: 982 gc time: 0
> > > 351
>
> > > I don't have Gambit, Bigloo or Stalin available right now, so
> > > getting down to C++ speed is difficult. I'm curious about your C++
> > > implementation though...
>
> > > --
> > > a game sig:http://tinyurl.com/d3rxz9
>
> > using your version (suitably translated to common lisp as necessary)
> > and the same inputs (1 100000) I get these timings for various scheme
> > and lisp implementations:
>
> > CCL: 0.334 seconds
> > LispWorks: 0.59 seconds
> > sbcl: 0.363 seconds
> > gambit: 2.626 seconds
> > mzscheme (jit): 1.9 seconds
> > larceny: 0.513
>
> OCaml: 0.161 seconds (on 2GHz laptop)
>
> let cycle_length n =
> let rec loop n length =
> if n > 1 then
> loop ( if n land 1 > 0 then 3*n + 1 else n / 2 ) (succ length)
> else length
> in loop n 1 ;;
>
> let max_cycle_length low high =
> let m = ref 0 in
> for n = low to high do
> m := max !m (cycle_length n)
> done ;
> !m ;;
More readable than Ruby, but when can we read your homework?
Cheers
--
Marco
On Apr 17, 5:28 pm, Raffael Cavallaro <················@gmail.com>
wrote:
> On Apr 17, 1:51 pm, namekuseijin <············@gmail.com> wrote:
>
>
>
>
>
> > Cross escreveu:
>
> > > I apologise for the confusion. My solution was not the ace solution. My solution
> > > is at 0.067 seconds.
>
> > > The input set is from 1 to 100000.
>
> > In Scheme:
>
> > ;http://icpcres.ecs.baylor.edu/onlinejudge/external/1/100.pdf
>
> > (define (cycle-length n)
> > (do ((i n (if (odd? i) (+ 1 (* 3 i)) (/ i 2)))
> > (length 1 (+ 1 length)))
> > ((= i 1) length)))
>
> > (define (max-cycle-length from to)
> > (do ((n from (+ 1 n))
> > (r 1 (max r (cycle-length n))))
> > ((> n to) r)))
>
> > Timings in one native-compiled implementation and one jit-compiled:
>
> > Larceny v0.97b1 (beta test) (Aug 25 2008 10:57:44, precise:Win32:unified)
> > larceny.heap, built on Mon 08/25/2008
>
> > > (load "uva-3n_plus_1-max-cycle-length.scm")
>
> > > (time (max-cycle-length 1 100000))
> > Words allocated: 0
> > Words reclaimed: 0
> > Elapsed time...: 468 ms (User: 468 ms; System: 0 ms)
> > Elapsed GC time: 0 ms (CPU: 0 in 0 collections.)
> > 351
>
> > Welcome to MzScheme v4.0.2 [3m], Copyright (c) 2004-2008 PLT Scheme Inc.
> > > (load "uva-3n_plus_1-max-cycle-length.scm")
> > > (time (max-cycle-length 1 100000))
> > cpu time: 1014 real time: 1014 gc time: 0
> > 351
> > > (time (max-cycle-length 1 100000))
> > cpu time: 983 real time: 982 gc time: 0
> > 351
>
> > I don't have Gambit, Bigloo or Stalin available right now, so getting
> > down to C++ speed is difficult. I'm curious about your C++
> > implementation though...
>
> > --
> > a game sig:http://tinyurl.com/d3rxz9
>
> Using your version and the same inputs (code minimally translated to
> common lisp of course as necessary):
>
> CCL: 0.334
> LispWorks: 0.596
> sbcl: 0.363
> larceny: 0.513
> mzscheme: 0.351
> gambit: 2.626
sorry if you see dupes - google groups was losing posts.
namekuseijin escreveu:
> Cross escreveu:
>> I apologise for the confusion. My solution was not the ace solution.
>> My solution
>> is at 0.067 seconds.
>>
>> The input set is from 1 to 100000.
>
> In Scheme:
>
> ; http://icpcres.ecs.baylor.edu/onlinejudge/external/1/100.pdf
>
> (define (cycle-length n)
> (do ((i n (if (odd? i) (+ 1 (* 3 i)) (/ i 2)))
> (length 1 (+ 1 length)))
> ((= i 1) length)))
>
> (define (max-cycle-length from to)
> (do ((n from (+ 1 n))
> (r 1 (max r (cycle-length n))))
> ((> n to) r)))
>
>
> Timings in one native-compiled implementation and one jit-compiled:
>
>
> Larceny v0.97b1 (beta test) (Aug 25 2008 10:57:44, precise:Win32:unified)
> larceny.heap, built on Mon 08/25/2008
>
> > (load "uva-3n_plus_1-max-cycle-length.scm")
>
> > (time (max-cycle-length 1 100000))
> Words allocated: 0
> Words reclaimed: 0
> Elapsed time...: 468 ms (User: 468 ms; System: 0 ms)
> Elapsed GC time: 0 ms (CPU: 0 in 0 collections.)
> 351
>
>
> Welcome to MzScheme v4.0.2 [3m], Copyright (c) 2004-2008 PLT Scheme Inc.
> > (load "uva-3n_plus_1-max-cycle-length.scm")
> > (time (max-cycle-length 1 100000))
> cpu time: 1014 real time: 1014 gc time: 0
> 351
> > (time (max-cycle-length 1 100000))
> cpu time: 983 real time: 982 gc time: 0
> 351
>
>
> I don't have Gambit, Bigloo or Stalin available right now, so getting
> down to C++ speed is difficult. I'm curious about your C++
> implementation though...
>
As way of comparison, here's it as measured in Python:
import timeit
t = timeit.Timer( "max_cycle_length( 1, 100000 )",
"""
def cycle_length( n ):
length=1
while(n>1):
#if odd(n): # yeah, who needs odd?
if 0!=n%2:
n=3*n+1
else:
n/=2
length+=1
return length
# lame keyword-based language: I simply can't use from...
def max_cycle_length( frm, to ):
return max(cycle_length(x) for x in range(frm,to+1))
""")
print( t.timeit(1) )
# -> 2.6627664968592377 on a Vista Core 2 Duo as the ones before...
I'm guessing parsing the statements from the strings is not taken into
account. I'll let William James provide the cryptic and slower Ruby
one-liner. ;)
--
a game sig: http://tinyurl.com/d3rxz9
Raffael Cavallaro escreveu:
> On Apr 17, 1:51 pm, namekuseijin <············@gmail.com> wrote:
>> Cross escreveu:
>>
>>> I apologise for the confusion. My solution was not the ace solution. My solution
>>> is at 0.067 seconds.
>>> The input set is from 1 to 100000.
>> In Scheme:
>>
>> ;http://icpcres.ecs.baylor.edu/onlinejudge/external/1/100.pdf
>>
>> (define (cycle-length n)
>> (do ((i n (if (odd? i) (+ 1 (* 3 i)) (/ i 2)))
>> (length 1 (+ 1 length)))
>> ((= i 1) length)))
>>
>> (define (max-cycle-length from to)
>> (do ((n from (+ 1 n))
>> (r 1 (max r (cycle-length n))))
>> ((> n to) r)))
>>
>> Timings in one native-compiled implementation and one jit-compiled:
>>
>> Larceny v0.97b1 (beta test) (Aug 25 2008 10:57:44, precise:Win32:unified)
>> larceny.heap, built on Mon 08/25/2008
>>
>> > (load "uva-3n_plus_1-max-cycle-length.scm")
>>
>> > (time (max-cycle-length 1 100000))
>> Words allocated: 0
>> Words reclaimed: 0
>> Elapsed time...: 468 ms (User: 468 ms; System: 0 ms)
>> Elapsed GC time: 0 ms (CPU: 0 in 0 collections.)
>> 351
>>
>> Welcome to MzScheme v4.0.2 [3m], Copyright (c) 2004-2008 PLT Scheme Inc.
>> > (load "uva-3n_plus_1-max-cycle-length.scm")
>> > (time (max-cycle-length 1 100000))
>> cpu time: 1014 real time: 1014 gc time: 0
>> 351
>> > (time (max-cycle-length 1 100000))
>> cpu time: 983 real time: 982 gc time: 0
>> 351
>>
>> I don't have Gambit, Bigloo or Stalin available right now, so getting
>> down to C++ speed is difficult. I'm curious about your C++
>> implementation though...
>>
>> --
>> a game sig:http://tinyurl.com/d3rxz9
>
> Using your version and the same inputs (code minimally translated to
> common lisp of course as necessary):
>
> CCL: 0.334
> LispWorks: 0.596
> sbcl: 0.363
> larceny: 0.513
> mzscheme: 0.351
> gambit: 2.626
What did you do to get mzscheme that fast? The timings I posted were on
Windows here at work so I'm kinda constrained on command-line options.
However, they are consistent with my timings on Linux, where mzscheme
always loses to larceny by about that rate, either with option jit or
not (when it performs much worse).
--
a game sig: http://tinyurl.com/d3rxz9
On Apr 17, 5:49 pm, namekuseijin <············@gmail.com> wrote:
> Raffael Cavallaro escreveu:
>
>
>
>
>
> > On Apr 17, 1:51 pm, namekuseijin <············@gmail.com> wrote:
> >> Cross escreveu:
>
> >>> I apologise for the confusion. My solution was not the ace solution. My solution
> >>> is at 0.067 seconds.
> >>> The input set is from 1 to 100000.
> >> In Scheme:
>
> >> ;http://icpcres.ecs.baylor.edu/onlinejudge/external/1/100.pdf
>
> >> (define (cycle-length n)
> >> (do ((i n (if (odd? i) (+ 1 (* 3 i)) (/ i 2)))
> >> (length 1 (+ 1 length)))
> >> ((= i 1) length)))
>
> >> (define (max-cycle-length from to)
> >> (do ((n from (+ 1 n))
> >> (r 1 (max r (cycle-length n))))
> >> ((> n to) r)))
>
> >> Timings in one native-compiled implementation and one jit-compiled:
>
> >> Larceny v0.97b1 (beta test) (Aug 25 2008 10:57:44, precise:Win32:unified)
> >> larceny.heap, built on Mon 08/25/2008
>
> >> > (load "uva-3n_plus_1-max-cycle-length.scm")
>
> >> > (time (max-cycle-length 1 100000))
> >> Words allocated: 0
> >> Words reclaimed: 0
> >> Elapsed time...: 468 ms (User: 468 ms; System: 0 ms)
> >> Elapsed GC time: 0 ms (CPU: 0 in 0 collections.)
> >> 351
>
> >> Welcome to MzScheme v4.0.2 [3m], Copyright (c) 2004-2008 PLT Scheme Inc.
> >> > (load "uva-3n_plus_1-max-cycle-length.scm")
> >> > (time (max-cycle-length 1 100000))
> >> cpu time: 1014 real time: 1014 gc time: 0
> >> 351
> >> > (time (max-cycle-length 1 100000))
> >> cpu time: 983 real time: 982 gc time: 0
> >> 351
>
> >> I don't have Gambit, Bigloo or Stalin available right now, so getting
> >> down to C++ speed is difficult. I'm curious about your C++
> >> implementation though...
>
> >> --
> >> a game sig:http://tinyurl.com/d3rxz9
>
> > Using your version and the same inputs (code minimally translated to
> > common lisp of course as necessary):
>
> > CCL: 0.334
> > LispWorks: 0.596
> > sbcl: 0.363
> > larceny: 0.513
> > mzscheme: 0.351
> > gambit: 2.626
>
> What did you do to get mzscheme that fast? The timings I posted were on
> Windows here at work so I'm kinda constrained on command-line options.
> However, they are consistent with my timings on Linux, where mzscheme
> always loses to larceny by about that rate, either with option jit or
> not (when it performs much worse).
>
> --
> a game sig:http://tinyurl.com/d3rxz9
Damn. This is what happens when Google Gropus loses posts and I have
to retype them!
That should be:
mzscheme (jitted): 1.9 seconds
and I rechecked the gsc compiled time, it really is 2.6 seconds, and
even with declarations:
(declare (not safe))
(declare (block))
(declare (standard-bindings))
(declare (not interrupts-enabled))
(declare (fixnum))
it's still 2.4 seconds
finally, here's a clojure version that takes 1.6 seconds:
(defn cycle-length [n]
(loop [i n
length 1]
(if (= i 1) length
(recur (if (odd? i) (+ 1 (* 3 i)) (/ i 2))
(+ 1 length)))))
(defn max-cycle-length [from to]
(loop [n from
r 1]
(if (> n to) r
(recur (+ 1 n) (max r (cycle-length n))))))
user=> (time (max-cycle-length 1 100000))
"Elapsed time: 1608.265 msecs"
351
and yes, this is with the server option, and I've warmed up hotspot
with a half dozen runs.
On Apr 17, 6:35 pm, Raffael Cavallaro <················@gmail.com>
wrote:
> That should be:
> mzscheme (jitted): 1.9 seconds
>
> and I rechecked the gsc compiled time, it really is 2.6 seconds, and
> even with declarations:
> (declare (not safe))
> (declare (block))
> (declare (standard-bindings))
> (declare (not interrupts-enabled))
> (declare (fixnum))
>
> it's still 2.4 seconds
With your code I get
(time (max-cycle-length 1 100000))
2159 ms real time
1800 ms cpu time (1792 user, 8 system)
2187 collections accounting for 151 ms real time (168 user, 8
system)
690139008 bytes allocated
132 minor faults
no major faults
and if I change (/ i 2) to (quotient i 2) I get
> (time (max-cycle-length 1 100000))
(time (max-cycle-length 1 100000))
36 ms real time
32 ms cpu time (32 user, 0 system)
no collections
no bytes allocated
1 minor fault
no major faults
The Gambit compiler doesn't do anything special with / on exact
arguments, it assumes that rational results are possible and calls the
library routine.
Brad
On Apr 17, 8:56 pm, Brad Lucier <······@math.purdue.edu> wrote:
> and if I change (/ i 2) to (quotient i 2) I get
>
> > (time (max-cycle-length 1 100000))
>
> (time (max-cycle-length 1 100000))
> 36 ms real time
> 32 ms cpu time (32 user, 0 system)
> no collections
> no bytes allocated
> 1 minor fault
> no major faults
And if you compile the new code without any declarations at all you
get
(time (max-cycle-length 1 100000))
169 ms real time
136 ms cpu time (136 user, 0 system)
no collections
no bytes allocated
5 minor faults
no major faults
On Apr 17, 9:11 pm, Brad Lucier <······@math.purdue.edu> wrote:
> On Apr 17, 8:56 pm, Brad Lucier <······@math.purdue.edu> wrote:
>
> > and if I change (/ i 2) to (quotient i 2) I get
>
> > > (time (max-cycle-length 1 100000))
>
> > (time (max-cycle-length 1 100000))
> > 36 ms real time
> > 32 ms cpu time (32 user, 0 system)
> > no collections
> > no bytes allocated
> > 1 minor fault
> > no major faults
>
> And if you compile the new code without any declarations at all you
> get
>
> (time (max-cycle-length 1 100000))
> 169 ms real time
> 136 ms cpu time (136 user, 0 system)
> no collections
> no bytes allocated
> 5 minor faults
> no major faults
yup, quotient is it. btw, with declaratons the gambit version is just
a hair slower than the bit-shift bummed c code:
results for 1 1000000 525:
cross's c version : 0.423 seconds
gambit with declarations and quotient: 0.549
Raffael Cavallaro wrote:
> On Apr 17, 9:11 pm, Brad Lucier <······@math.purdue.edu> wrote:
>> On Apr 17, 8:56 pm, Brad Lucier <······@math.purdue.edu> wrote:
>>
>>> and if I change (/ i 2) to (quotient i 2) I get
>>>> (time (max-cycle-length 1 100000))
>>> (time (max-cycle-length 1 100000))
>>> 36 ms real time
>>> 32 ms cpu time (32 user, 0 system)
>>> no collections
>>> no bytes allocated
>>> 1 minor fault
>>> no major faults
>> And if you compile the new code without any declarations at all you
>> get
>>
>> (time (max-cycle-length 1 100000))
>> 169 ms real time
>> 136 ms cpu time (136 user, 0 system)
>> no collections
>> no bytes allocated
>> 5 minor faults
>> no major faults
>
> yup, quotient is it. btw, with declaratons the gambit version is just
> a hair slower than the bit-shift bummed c code:
>
> results for 1 1000000 525:
>
> cross's c version : 0.423 seconds
> gambit with declarations and quotient: 0.549
Now that's what I'm talking about! Gambit/Stalin/Bigloo is da shizznit! :D
And the good thing is that the (few) declarations are simply copy-paste
to the top, no need to rework the code in any way or perform silly,
cryptic and verbose black magic.
Raffael Cavallaro wrote:
> yup, quotient is it. btw, with declaratons the gambit version is just
> a hair slower than the bit-shift bummed c code:
>
> results for 1 1000000 525:
>
> cross's c version : 0.423 seconds
> gambit with declarations and quotient: 0.549
>
Well don't take my code for comparison only because I started the thread. I did
mention that my implementation is poor and that the ace solution takes 0.000 cpu
seconds. This is what you should target not my poor code.
Cross wrote:
>> cross's c version : 0.423 seconds
>> gambit with declarations and quotient: 0.549
>>
>
> Well don't take my code for comparison only because I started the thread. I did
> mention that my implementation is poor and that the ace solution takes 0.000 cpu
> seconds. This is what you should target not my poor code.
What ace solution? Does that mean it is more assembly and obfuscated
than yours? Is it worth taking all the pain to come up with an
incomprehensible write-only hack just to save a few milliseconds that
Moore's law will deal with anyway?
namekuseijin wrote:
> Cross wrote:
>>> cross's c version : 0.423 seconds
>>> gambit with declarations and quotient: 0.549
>>>
>>
>> Well don't take my code for comparison only because I started the
>> thread. I did
>> mention that my implementation is poor and that the ace solution takes
>> 0.000 cpu
>> seconds. This is what you should target not my poor code.
>
> What ace solution? Does that mean it is more assembly and obfuscated
> than yours? Is it worth taking all the pain to come up with an
> incomprehensible write-only hack just to save a few milliseconds that
> Moore's law will deal with anyway?
http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&page=problem_stats&problemid=36&category=3
Well I do not know what the ace solution is. I do not know if it is assembly or
not. I am genuinely interested in getting it done in Lisp.
Cross wrote:
> http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&page=problem_stats&problemid=36&category=3
> Well I do not know what the ace solution is. I do not know if it is assembly or
> not. I am genuinely interested in getting it done in Lisp.
Just registered there now. It only accepts submissions in C, C++, Java
and Pascal, so, no point. C generated from Gambit needs libgambc.
In any case, I think it very hard to believe that one of those inputs is
from 1 to 1,000,000 and the timing rest below 0.000 sec.
On 18 abr, 20:33, namekuseijin <···················@gmail.com> wrote:
> Cross wrote:
> >http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_online...
> > Well I do not know what the ace solution is. I do not know if it is assembly or
> > not. I am genuinely interested in getting it done in Lisp.
>
> Just registered there now. It only accepts submissions in C, C++, Java
> and Pascal, so, no point. C generated from Gambit needs libgambc.
>
> In any case, I think it very hard to believe that one of those inputs is
> from 1 to 1,000,000 and the timing rest below 0.000 sec.
A specific way of memoization used for this problem can be found
in wikipedia: http://en.wikipedia.org/wiki/Collatz_conjecture look
there at optimizations.
On Apr 18, 11:33 am, namekuseijin <···················@gmail.com>
wrote:
> Cross wrote:
> >http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_online...
> > Well I do not know what the ace solution is. I do not know if it is assembly or
> > not. I am genuinely interested in getting it done in Lisp.
>
> Just registered there now. It only accepts submissions in C, C++, Java
> and Pascal, so, no point. C generated from Gambit needs libgambc.
>
> In any case, I think it very hard to believe that one of those inputs is
> from 1 to 1,000,000 and the timing rest below 0.000 sec.
Thinking about it... it should be possible, even in languages that are
stereotyped as slow. The trick is to do as much as possible at
compile time.
The algorithm would be:
1) Generate the cycle numbers for every value from 1 to 2^10 in a
giant array (vector) at compile time.
2) Generate a second array of cumulative maxima of every second
adjacent pair of input values ie. max(cycles(1), cycles(2)), max(cycles
(3), cycles(4)), max(cycles(5), cycles(6)), etc.
3) Generate a third array of cumulative maxima out of every four
adjacent sets of four input values.
4) Repeat for sets of 8, 16, 32... and so on up to the cumulative set
of all the possible input numbers. Do this all at compile time. The
total space taken will "only" be twice that of the first array.
5) At runtime, get your two boundary values.
6) Use these to recursively "clip" to the cumulative maxima going down
in size range by factors of two at each step.
This takes O(log(n)) comparisons and memory reads to do the
calculation at runtime at the cost of O(n) of memory. This algorithm
may be slower than the obvious way if the two input numbers are very
small. It also may not be useful if the range of input values is too
large. However, if the maximum input value is only a million, then it
will work quite well. No asm required.
On Sat, 18 Apr 2009 15:28:39 -0700, svfuerst wrote:
> On Apr 18, 11:33 am, namekuseijin <···················@gmail.com> wrote:
>> Cross wrote:
>> >http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_online...
>> > Well I do not know what the ace solution is. I do not know if it is
>> > assembly or not. I am genuinely interested in getting it done in
>> > Lisp.
>>
>> Just registered there now. It only accepts submissions in C, C++, Java
>> and Pascal, so, no point. C generated from Gambit needs libgambc.
>>
>> In any case, I think it very hard to believe that one of those inputs
>> is from 1 to 1,000,000 and the timing rest below 0.000 sec.
>
> Thinking about it... it should be possible, even in languages that are
> stereotyped as slow. The trick is to do as much as possible at compile
> time.
>
> The algorithm would be:
> 1) Generate the cycle numbers for every value from 1 to 2^10 in a giant
> array (vector) at compile time. 2) Generate a second array of cumulative
> maxima of every second adjacent pair of input values ie. max(cycles(1),
> cycles(2)), max(cycles (3), cycles(4)), max(cycles(5), cycles(6)), etc.
> 3) Generate a third array of cumulative maxima out of every four
> adjacent sets of four input values.
> 4) Repeat for sets of 8, 16, 32... and so on up to the cumulative set of
> all the possible input numbers. Do this all at compile time. The total
> space taken will "only" be twice that of the first array. 5) At runtime,
> get your two boundary values. 6) Use these to recursively "clip" to the
> cumulative maxima going down in size range by factors of two at each
> step.
>
> This takes O(log(n)) comparisons and memory reads to do the calculation
> at runtime at the cost of O(n) of memory. This algorithm may be slower
> than the obvious way if the two input numbers are very small. It also
> may not be useful if the range of input values is too large. However,
> if the maximum input value is only a million, then it will work quite
> well. No asm required.
Quite clever. This reinforces the following beliefs I have always held:
1) benchmarks are almost useless, especially for differences smaller
than an order of magnitude,
2) improving the algorithm usually has higher returns than the
tweaking of the code people usually refer to as "optimizing"
And of course Common Lisp really shines when you want to make
significant changes to your code cheaply. Fortran or C may be
"faster", but most programs I have seen in either are quite brittle
and resistant to major changes. That's why I am using CL for
numerical computations.
Tamas
Tamas K Papp wrote:
> That's why I am using CL for
> numerical computations.
>
> Tamas
Thats interesting. As far as I know, for numerical computations, you are better
off using languages like FORTRAN and C. Well, I have heard folks at NASA use them.
On Sun, 19 Apr 2009 19:58:35 +0530, Cross wrote:
> Tamas K Papp wrote:
>> That's why I am using CL for
>> numerical computations.
>>
>> Tamas
>
> Thats interesting. As far as I know, for numerical computations, you are
> better off using languages like FORTRAN and C. Well, I have heard folks
> at NASA use them.
Maybe they are doing something different. Most people I know prefer
using dynamic, interactive environments (R, Matlab, etc). Of course
the underlying operations may be coded in Fortran/C for speed (I call
LAPACK and UMFpack from CL, too), but for higher-level code, Fortran
and C are a pain in the rear end.
I used R before, and coded bottlenecks in C. Then I found that most
of the time I spent programming was on debugging the interface between
the two for memory leaks. Then I found CL, which is a nice high-level
language _and_ you can also compile it and make it fast, best of both
worlds.
Tamas
On Apr 19, 5:15 pm, Tamas K Papp <······@gmail.com> wrote:
> I used R before, and coded bottlenecks in C. Then I found that most
> of the time I spent programming was on debugging the interface between
> the two for memory leaks. Then I found CL, which is a nice high-level
> language _and_ you can also compile it and make it fast, best of both
> worlds.
Not to mention the interaction of common lisp and C through the FFI
when needed. My collegues had tears in their eyes when I showed them
how to embed C libraries and C programs into ECL. Complicated computer
intensive programs were run to completion in less than a second. I
still use R though because a lot of statisticians publish their codes
in R. What I do is translate what I find useful into C and/or CL.
On 19 Apr 2009 15:15:19 GMT, <······@gmail.com> wrote:
> On Sun, 19 Apr 2009 19:58:35 +0530, Cross wrote:
>
>> Tamas K Papp wrote:
>>> That's why I am using CL for
>>> numerical computations.
>>>
>>> Tamas
>>
>> Thats interesting. As far as I know, for numerical computations, you are
>> better off using languages like FORTRAN and C. Well, I have heard folks
>> at NASA use them.
Sounds like you have NEVER met a NASA researcher.
> Maybe they are doing something different. Most people I know prefer
> using dynamic, interactive environments (R, Matlab, etc). Of course
> the underlying operations may be coded in Fortran/C for speed (I call
> LAPACK and UMFpack from CL, too), but for higher-level code, Fortran
> and C are a pain in the rear end.
Most Fortran users are not writing code, but simply running legacy
code. 'Legacy' is pretty important for many research fields,
e.g. heart monitoring, traces are still reproduced in the classical 3
point system, despite it's drawbacks and current multi-point practice.
People writing new numerical code have chosen lisp, I was just viewing
some cryptoanalysis the other day, and then there is Koza.
--
Lisp: Powering `Impossible Thoughts since 1958
On Apr 19, 7:36 pm, GP lisper <········@CloudDancer.com> wrote:
> On 19 Apr 2009 15:15:19 GMT, <······@gmail.com> wrote:
>
> > On Sun, 19 Apr 2009 19:58:35 +0530, Cross wrote:
>
> >> Tamas K Papp wrote:
> >>> That's why I am using CL for
> >>> numerical computations.
>
> >>> Tamas
>
> >> Thats interesting. As far as I know, for numerical computations, you are
> >> better off using languages like FORTRAN and C. Well, I have heard folks
> >> at NASA use them.
>
> Sounds like you have NEVER met a NASA researcher.
I did. He is a friend who gave me a Deep Space 1 T-shirt. They wrote
(some of) the code in.....
Cheers
--
Marco
On Sun, 19 Apr 2009 10:36:13 -0700, GP lisper wrote:
> People writing new numerical code have chosen lisp, I was just viewing
> some cryptoanalysis the other day, and then there is Koza.
Forgive my ignorance, but what is Koza?
Tamas
On Apr 19, 3:51 pm, Tamas K Papp <······@gmail.com> wrote:
> On Sun, 19 Apr 2009 10:36:13 -0700, GP lisper wrote:
> > People writing new numerical code have chosen lisp, I was just viewing
> > some cryptoanalysis the other day, and then there is Koza.
>
> Forgive my ignorance, but what is Koza?
>
> Tamas
<http://en.wikipedia.org/wiki/John_Koza>
<http://www.genetic-programming.com/johnkoza.html>
His genetic programming code was written in lisp.
BTW, I just read on his website that he is also the co-inventor of the
lottery scratch card.
Cross wrote:
> Tamas K Papp wrote:
>> That's why I am using CL for
>> numerical computations.
>>
>> Tamas
>
> Thats interesting. As far as I know, for numerical computations, you are better
> off using languages like FORTRAN and C. Well, I have heard folks at NASA use them.
The people at CERN are using dynamic C++ called CINT with a huge library
called ROOT.
Check it out in http://root.cern.ch
but it's quite heavy, and the interpretter is 1000 slower, but the
system allows to selectivelly choose which piece is compiled, and which
one is not. For example if you work on a game, in a team with 20
programmers, and you are doing say the AI, you can compile the rest of
the stuff...
Tamas K Papp <······@gmail.com> writes:
> 2) improving the algorithm usually has higher returns than the
> tweaking of the code people usually refer to as "optimizing"
Speaking of which, has anybody tried a memoizing approach to this
particular problem? It seems that particularly with some of the larger
runs in this, and also when going over different ranges, that there is a
potential for duplication of intermediate results.
--
Thomas A. Russ, USC/Information Sciences Institute
Cross <·@X.tv> writes:
> Raffael Cavallaro wrote:
>
>> yup, quotient is it. btw, with declaratons the gambit version is just
>> a hair slower than the bit-shift bummed c code:
>>
>> results for 1 1000000 525:
>>
>> cross's c version : 0.423 seconds
>> gambit with declarations and quotient: 0.549
>>
>
> Well don't take my code for comparison only because I started the
> thread. I did mention that my implementation is poor and that the ace
> solution takes 0.000 cpu seconds. This is what you should target not
> my poor code.
It can't possibly run in 0 seconds if it does something, it has to take
time to do it. You should really think about doing a proper measurement
if you want to compare times.
> It can't possibly run in 0 seconds if it does something, it has to take
> time to do it. You should really think about doing a proper measurement
> if you want to compare times.
Good catch :) This is the crux of the problem: Microbenchmarking without
microscope!
At least for the sake of microbenchmarking, the original poster could've
looped through the whole test a couple of times.
Dimiter "malkia" Stanev wrote:
>> It can't possibly run in 0 seconds if it does something, it has to take
>> time to do it. You should really think about doing a proper measurement
>> if you want to compare times.
>
> Good catch :) This is the crux of the problem: Microbenchmarking without
> microscope!
>
> At least for the sake of microbenchmarking, the original poster could've
> looped through the whole test a couple of times.
Well I posted the result from the UVa server.
Cross <·@X.tv> writes:
> Dimiter "malkia" Stanev wrote:
>>> It can't possibly run in 0 seconds if it does something, it has to take
>>> time to do it. You should really think about doing a proper measurement
>>> if you want to compare times.
>>
>> Good catch :) This is the crux of the problem: Microbenchmarking without
>> microscope!
>>
>> At least for the sake of microbenchmarking, the original poster could've
>> looped through the whole test a couple of times.
> Well I posted the result from the UVa server.
I know, but seeing "0.000" seconds over and over was driving me nuts,
whether it was the result of your testing or theirs.
Good call! quotient rather than / indeed brings a bit more performance
to about most Schemes.
And thanks for clarifying the gambit timing, it'd be certainly quite
remarkable and unbelievable if it were to perform the worst.
Cross pisze:
> Recently, I was trying the problems at the UVa website. As is the case with
> many, my first problem was the 3n+1 problem. After solving it I found that the
> best solution for the problem had a runtime of 0.000 seconds. That solution was
> in C++. I was wondering if fast programs like that are possible in Lisp. If you
> think it is, I request you to share your code with me. I also welcome guidance
> in this regard.
I am new to lisp and written this as exercise. If code is
horribly written (as my English for example :) then hints,
improvements and bugfixes are welcome.
(defun cycles (n)
(do ((counter 1 (+ counter 1))
(nth n (cond ((oddp nth) (+ (* 3 nth) 1))
(t (/ nth 2)))))
((= nth 1) counter)))
(defun max-cycles (n1 n2)
(do* ((n n1 (+ n 1))
(cycles (cycles n) (cycles n))
(max 1 (if (< max cycles)
cycles
max)))
((> n n2) (list n1 n2 max))))
You dont reference exact definition of problem, then I cant
run it with Your input but below I give timings for few inputs.
Code is not optimized at all, ran on Clozure CL, Windows XP,
Athlon 2,3 GHz processor.
(time (max-cycles 1 10000))
(MAX-CYCLES 1 10000) took 0 milliseconds (0.000 seconds) to run
with 2 available CPU cores.
During that period, 32 milliseconds (0.032 seconds) were spent in user mode
0 milliseconds (0.000 seconds) were spent in system
mode
24 bytes of memory allocated.
(1 10000 262)
(time (max-cycles 1 1000000))
(MAX-CYCLES 1 1000000) took 6,000 milliseconds (6.000 seconds) to run
with 2 available CPU cores.
During that period, 6,078 milliseconds (6.078 seconds) were spent in
user mode
0 milliseconds (0.000 seconds) were spent in system
mode
311,136 bytes of memory allocated.
(1 1000000 525)
Piotr Chamera wrote:
> I am new to lisp and written this as exercise. If code is
> horribly written (as my English for example :) then hints,
> improvements and bugfixes are welcome.
>
> (defun cycles (n)
> (do ((counter 1 (+ counter 1))
> (nth n (cond ((oddp nth) (+ (* 3 nth) 1))
> (t (/ nth 2)))))
> ((= nth 1) counter)))
This is just a matter of style: cond is not needed when there are only
2 clauses. A simple if will do with far less clutter. :)
> You dont reference exact definition of problem, then I cant
> run it with Your input but below I give timings for few inputs.
Above in the thread he explains the input and even give the
almost-assembly C code he used.
> Code is not optimized at all, ran on Clozure CL, Windows XP,
> Athlon 2,3 GHz processor.
>
> (time (max-cycles 1 1000000))
> (MAX-CYCLES 1 1000000) took 6,000 milliseconds (6.000 seconds) to run
> with 2 available CPU cores.
> During that period, 6,078 milliseconds (6.078 seconds) were spent in
> user mode
> 0 milliseconds (0.000 seconds) were spent in system
> mode
> 311,136 bytes of memory allocated.
> (1 1000000 525)
Fun. All best Lisps and Schemes seem to give about the same timings for
the straightforward algorithm as stated in the paper. None however
getting close to the speed of the C version he posted:
#include <stdio.h>
unsigned int cycles(register unsigned int n){
if(n&1){
if(n==1)return 1;
else{
n+=(n+1)>>1;
return cycles(n)+2;
/*the next one will obviously be odd, so we can add two cycles
and skip a funtion call*/
}
}else
return cycles(n>>1)+1;
}
int main(){
unsigned int i, j;
register unsigned int max, r, t;
int c;
while((c=getchar())!=EOF){
ungetc(c, stdin);
scanf("%u%u\n", &i, &j);
max=0;
if(i<j){
t=i;
do{
if((r=cycles(t++))>max)max=r;
}while(t<=j);
}else{
t=j;
do{
if((r=cycles(t++))>max)max=r;
}while(t<=i);
}
printf("%u %u %u\n", i, j, max);
}
return 0;
}
Many black C magic with bit shifting, register variables and some smarty
loop choice of steps. I compiled it here on my Q6600 with gcc -O2 and
it ran by reading 1 and 1000000 from stdin.
Still, did not get anywhere near his original claimed 0.067 sec mark on
a Core 2 Duo, I got:
············@nameku:~/dev/scheme$ time ./uva-3np1 < uva-3nplus1.txt
1 1000000 525
real 0m0.361s
user 0m0.360s
sys 0m0.000s
on a Q6600. My best performant output code so far from a Scheme
implementation, with larceny, was about 17x slower:
> (quotient 6289 361)
17
Well, on a brighter note, our code is much more sane. :)
I could not just stop here by wondering how a "sane" C version would
behave. Turns out to be not much worse:
#include <stdio.h>
unsigned int cycle_length(unsigned int n)
{
unsigned int length;
length = 0;
while(n>1)
{
n = (0!=n%2)? 3*n+1 : n/2;
length++;
}
return length;
}
int main(){
unsigned int from, to, i;
unsigned int max, r;
int c;
while((c=getchar())!=EOF){
ungetc(c, stdin);
scanf("%u%u\n", &from, &to);
max=0;
/* assuming from always < to */
i=from;
do{
if ((r=cycle_length(i++)) > max) max=r;
} while (i<=to);
printf("%u %u %u\n", from, to, max+1);
}
return 0;
}
············@nameku:~/dev/scheme$ gcc -O2 uva-3np1-sane.c -o uva-3np1-sane
············@nameku:~/dev/scheme$ time ./uva-3np1-sane < uva-3nplus1.txt
1 1000000 525
real 0m0.437s
user 0m0.436s
sys 0m0.000s
············@nameku:~/dev/scheme$ time ./uva-3np1-sane < uva-3nplus1.txt
1 1000000 525
real 0m0.437s
user 0m0.436s
sys 0m0.000s
On Apr 17, 10:33 pm, namekuseijin <···················@gmail.com>
wrote:
> Fun. All best Lisps and Schemes seem to give about the same timings for
> the straightforward algorithm as stated in the paper. None however
> getting close to the speed of the C version he posted:
>
> #include <stdio.h>
> unsigned int cycles(register unsigned int n){
> if(n&1){
> if(n==1)return 1;
> else{
> n+=(n+1)>>1;
> return cycles(n)+2;
> /*the next one will obviously be odd, so we can add two cycles
> and skip a funtion call*/
> }
> }else
> return cycles(n>>1)+1;}
>
> int main(){
> unsigned int i, j;
> register unsigned int max, r, t;
> int c;
>
> while((c=getchar())!=EOF){
> ungetc(c, stdin);
> scanf("%u%u\n", &i, &j);
> max=0;
> if(i<j){
> t=i;
> do{
> if((r=cycles(t++))>max)max=r;
> }while(t<=j);
> }else{
> t=j;
> do{
> if((r=cycles(t++))>max)max=r;
> }while(t<=i);
> }
> printf("%u %u %u\n", i, j, max);
> }
> return 0;
>
> }
Again on my Xeon server somewhere at Purdue:
pythagoras-21% gcc -O3 -Wall -W -o crap crap.c
pythagoras-24% time ./crap << EOF
? 1 100000
? EOF
1 100000 351
0.016u 0.000s 0:00.04 25.0% 0+0k 0+0io 0pf+0w
And Gambit (using quotient) took
(time (max-cycle-length 1 100000))
36 ms real time
32 ms cpu time (32 user, 0 system)
no collections
no bytes allocated
1 minor fault
no major faults
So it's twice as fast as Gambit with declarations and < 10 times as
fast as generic safe Gambit code.
> #include <stdio.h>
>
> unsigned int cycle_length(unsigned int n)
> {
> unsigned int length;
> length = 0;
> while(n>1)
> {
> n = (0!=n%2)? 3*n+1 : n/2;
> length++;
> }
> return length;
>
> }
>
> int main(){
> unsigned int from, to, i;
> unsigned int max, r;
> int c;
>
> while((c=getchar())!=EOF){
> ungetc(c, stdin);
> scanf("%u%u\n", &from, &to);
> max=0;
> /* assuming from always < to */
> i=from;
> do{
> if ((r=cycle_length(i++)) > max) max=r;
> } while (i<=to);
> printf("%u %u %u\n", from, to, max+1);
> }
> return 0;
>
> }
and this ran even faster (if one can get consistent numbers from
"benchmarks" that take about 0.01 seconds)
pythagoras-31% gcc -O3 -Wall -W -o crap2 crap2.c
pythagoras-32% time ./crap << EOF
? 1 100000
? EOF
1 100000 351
0.012u 0.000s 0:00.02 50.0% 0+0k 0+0io 0pf+0w
So C is twice as fast as Scheme, if you run Scheme with the same
semantics (unsafe operations, type declarations, ...).
Again.
Brad
namekuseijin wrote:
> Many black C magic with bit shifting, register variables and some smarty
> loop choice of steps. I compiled it here on my Q6600 with gcc -O2 and
> it ran by reading 1 and 1000000 from stdin.
>
> Still, did not get anywhere near his original claimed 0.067 sec mark on
> a Core 2 Duo, I got:
>
> ············@nameku:~/dev/scheme$ time ./uva-3np1 < uva-3nplus1.txt
> 1 1000000 525
>
> real 0m0.361s
> user 0m0.360s
> sys 0m0.000s
>
> on a Q6600. My best performant output code so far from a Scheme
> implementation, with larceny, was about 17x slower:
Well I quoted the server time. It is likely that the server uses a smaller set
of numbers within this bound. I am not very sure of this because the tests of
the server aren't known.
On 2009-04-17, Cross <·@X.tv> wrote:
> Hello
>
> Recently, I was trying the problems at the UVa website. As is the case with
> many, my first problem was the 3n+1 problem. After solving it I found that the
> best solution for the problem had a runtime of 0.000 seconds.
Stating the result this way is not useful, since zero is not considered to
have significant figures. There is no difference between 0, 0.0 and 0.000.
0.000 is not an accepted scientific or engineering notation for ``three
significant figures of zero''.
The notation 0.000 suggests that the time may be as small as a tiny iota above
zero, or as large as 0.000499... The percentage difference between these two
extremes is huge: the fastest time that could be written as 0.000 is
astronomically faster than the slowest time which could be written that way.
This is the crux of why you should not express near-zero results this way.
If your measurement registers zero, you must obtain a more precise measurement,
such that there is at least one non-zero digit---let's call it D. Then you can
write the result in the form 0.000D, or in exponential notation D x 10-4 .
> That solution was
> in C++. I was wondering if fast programs like that are possible in Lisp.
A program that takes zero time to run must be made of zero machine
instructions. As such, it processes no input and produces no output.
:)
Kaz Kylheku wrote:
> On 2009-04-17, Cross <·@X.tv> wrote:
>> Hello
>>
>> Recently, I was trying the problems at the UVa website. As is the case with
>> many, my first problem was the 3n+1 problem. After solving it I found that the
>> best solution for the problem had a runtime of 0.000 seconds.
>
> Stating the result this way is not useful, since zero is not considered to
> have significant figures. There is no difference between 0, 0.0 and 0.000.
> 0.000 is not an accepted scientific or engineering notation for ``three
> significant figures of zero''.
>
I should have clarified that the time taken by the ace solution is less than 1
millisecond. Target your code at that. :-)
> This is the crux of why you should not express near-zero results this way.
>
It is the UVa server's notation not mine and I understand the limitation.
On 18 abr, 09:00, Cross <····@X.tv> wrote:
> Kaz Kylheku wrote:
> > On 2009-04-17, Cross <····@X.tv> wrote:
> >> Hello
>
> >> Recently, I was trying the problems at the UVa website. As is the case with
> >> many, my first problem was the 3n+1 problem. After solving it I found that the
> >> best solution for the problem had a runtime of 0.000 seconds.
>
> > Stating the result this way is not useful, since zero is not considered to
> > have significant figures. There is no difference between 0, 0.0 and 0.000.
> > 0.000 is not an accepted scientific or engineering notation for ``three
> > significant figures of zero''.
>
> I should have clarified that the time taken by the ace solution is less than 1
> millisecond. Target your code at that. :-)> This is the crux of why you should not express near-zero results this way.
>
> It is the UVa server's notation not mine and I understand the limitation.
You can use memoization to speed the code.
Too lazy to do it now.
http://en.wikipedia.org/wiki/Memoization
On 18 abr, 11:53, camponoblanco <·············@gmail.com> wrote:
> On 18 abr, 09:00, Cross <····@X.tv> wrote:
>
>
>
> > Kaz Kylheku wrote:
> > > On 2009-04-17, Cross <····@X.tv> wrote:
> > >> Hello
>
> > >> Recently, I was trying the problems at the UVa website. As is the case with
> > >> many, my first problem was the 3n+1 problem. After solving it I found that the
> > >> best solution for the problem had a runtime of 0.000 seconds.
>
> > > Stating the result this way is not useful, since zero is not considered to
> > > have significant figures. There is no difference between 0, 0.0 and 0.000.
> > > 0.000 is not an accepted scientific or engineering notation for ``three
> > > significant figures of zero''.
>
> > I should have clarified that the time taken by the ace solution is less than 1
> > millisecond. Target your code at that. :-)> This is the crux of why you should not express near-zero results this way.
>
> > It is the UVa server's notation not mine and I understand the limitation.
>
> You can use memoization to speed the code.
> Too lazy to do it now.
>
> http://en.wikipedia.org/wiki/Memoization
1.-) There is a memoization library in common lisp at that url.
Just for fun, use this problem for going to the zoo or launching a
rocket.
Going to the zoo: to suggest an algorithm for children going round
the zoo. ( The child choose a number and visit the Numbered cages
following the algorithm 3n+1, they want a long visit)
To launch a rocket. Choose the initial number so that applying
repeatedly the 3n+1 algorithm the number goes to the moon.
Third, what happen to the rocket when it reach its maximum?
it is a random walk? Consult Feller book to stimate when will it
land.
Can you relate this problem to a caotic one, for example Newton
method for solving equations. Try to find repulsive and attractive
forces and think if this can make a fractal.
Modify the problem, a new version with real numbers ...
Look a freerisk idea, (Toby segaran and ...). Put the problem
launching the rocket in order to filter the ranting agencies.
(All of this is a joke, no time to elaborate. Good Saturday to
everyone,).
If you have some extra time, try to relate this to Group theory,
unimodular form, Gauss reciprocity theorem in number theory, try to
get intuition about a way to measure how much symmetric there is in
this problem in order to apply Group theory or transformation
methods. Do all of this before breakfast.
On 18 Apr, 11:53, camponoblanco <·············@gmail.com> wrote:
> You can use memoization to speed the code.
> Too lazy to do it now.
>
> http://en.wikipedia.org/wiki/Memoization
It's not obvious that you can take advantage of memoization here -
some quick tests did not give good results.
--
(espen)
On Apr 18, 5:12 am, ·····@vestre.net wrote:
> On 18 Apr, 11:53, camponoblanco <·············@gmail.com> wrote:
>
> > You can use memoization to speed the code.
> > Too lazy to do it now.
>
> > http://en.wikipedia.org/wiki/Memoization
>
> It's not obvious that you can take advantage of memoization here -
> some quick tests did not give good results.
>
> --
> (espen)
The C version is about 8 times faster if you use memoization:
#include <stdio.h>
#include <stdlib.h>
static inline size_t ffsq(size_t x)
{
size_t result;
asm ("bsfq %[x], %[result]"
: [result] "=r" (result)
: [x] "mr" (x));
return result;
}
static unsigned cycles(unsigned long n, unsigned *memo)
{
size_t r = ffsq(n);
n >>= r;
if (n < 1000000)
{
unsigned c;
unsigned long on;
if (memo[n]) return memo[n] + r;
on = n;
n += (n+1)>>1;
c = cycles(n, memo) + 2 + r;
memo[on] = c;
return c;
}
n += (n+1)>>1;
return cycles(n, memo) + 2 + r;
}
static int usage(void)
{
printf("orig n1 n2\n");
exit(1);
}
int main(int argc, char **argv)
{
unsigned i, j;
unsigned max, r, t;
int c;
unsigned *memo = calloc(sizeof(unsigned) * 1000000, 1);
if (argc < 3) usage();
i = atoi(argv[1]);
j = atoi(argv[2]);
if (i > j)
{
unsigned tmp = i;
i = j;
j = tmp;
}
max = 0;
memo[1] = 1;
memo[3] = 8;
memo[5] = 6;
memo[7] = 17;
memo[9] = 20;
memo[11] = 15;
memo[13] = 10;
memo[15] = 18;
memo[17] = 13;
memo[19] = 21;
for (t = i; t <= j; t++)
{
r = cycles(t, memo);
if (r > max) max = r;
}
printf("%u %u %u\n", i, j, max);
free(memo);
return 0;
}
To go even faster - the result of cycles() for each number can be
calculated at compile time. Then a simple scan of the resulting array
can be used.
For even more speed, you can convert the result to floats, and use sse
to scan four numbers at a time using the maxps instruction.
········@gmail.com wrote:
> On Apr 18, 5:12 am, ·····@vestre.net wrote:
>> On 18 Apr, 11:53, camponoblanco <·············@gmail.com> wrote:
>>
>>> You can use memoization to speed the code.
>>> Too lazy to do it now.
>>> http://en.wikipedia.org/wiki/Memoization
>> It's not obvious that you can take advantage of memoization here -
>> some quick tests did not give good results.
>>
>> --
>> (espen)
>
> The C version is about 8 times faster if you use memoization:
>
> #include <stdio.h>
> #include <stdlib.h>
>
> static inline size_t ffsq(size_t x)
> {
> size_t result;
>
> asm ("bsfq %[x], %[result]"
> : [result] "=r" (result)
> : [x] "mr" (x));
>
> return result;
> }
>
> static unsigned cycles(unsigned long n, unsigned *memo)
> {
> size_t r = ffsq(n);
> n >>= r;
>
> if (n < 1000000)
> {
> unsigned c;
> unsigned long on;
>
> if (memo[n]) return memo[n] + r;
>
> on = n;
>
> n += (n+1)>>1;
> c = cycles(n, memo) + 2 + r;
> memo[on] = c;
> return c;
> }
>
> n += (n+1)>>1;
> return cycles(n, memo) + 2 + r;
> }
>
> static int usage(void)
> {
> printf("orig n1 n2\n");
> exit(1);
> }
>
> int main(int argc, char **argv)
> {
> unsigned i, j;
> unsigned max, r, t;
> int c;
>
> unsigned *memo = calloc(sizeof(unsigned) * 1000000, 1);
>
> if (argc < 3) usage();
>
> i = atoi(argv[1]);
> j = atoi(argv[2]);
>
> if (i > j)
> {
> unsigned tmp = i;
> i = j;
> j = tmp;
> }
> max = 0;
>
> memo[1] = 1;
> memo[3] = 8;
> memo[5] = 6;
> memo[7] = 17;
> memo[9] = 20;
> memo[11] = 15;
> memo[13] = 10;
> memo[15] = 18;
> memo[17] = 13;
> memo[19] = 21;
>
> for (t = i; t <= j; t++)
> {
> r = cycles(t, memo);
> if (r > max) max = r;
> }
>
> printf("%u %u %u\n", i, j, max);
>
> free(memo);
>
> return 0;
> }
>
> To go even faster - the result of cycles() for each number can be
> calculated at compile time. Then a simple scan of the resulting array
> can be used.
>
> For even more speed, you can convert the result to floats, and use sse
> to scan four numbers at a time using the maxps instruction.
That's not C anymore: I spot an asm.
For even more speed, I can wait 2 hours for my intelligible, concise and
non-obfuscated Lisp program to calculate the result for
(max-cycle-length 1
100000000000000000000000000000000000000000000000000000) while your
unsigned int program crashes and then feed that result as a string
constant to an non-obfuscated C program specialized for that same sole
input and have it run in 0.000000000000000000000000000000000000000000001
milliseconds.
<snip>
> > To go even faster - the result of cycles() for each number can be
> > calculated at compile time. Then a simple scan of the resulting array
> > can be used.
>
> > For even more speed, you can convert the result to floats, and use sse
> > to scan four numbers at a time using the maxps instruction.
>
> That's not C anymore: I spot an asm.
and? Who cares what language you use to solve this problem. The aim
is to find the fastest algorithm to run on the machine you have,
within the coding time available. If you can write a meta-program
that produces super-optimized output that solves the problem quicker
than anything else, it's still a valid solution. (And if it is
quicker than everything else, then it is a winning solution.)
>
> For even more speed, I can wait 2 hours for my intelligible, concise and
> non-obfuscated Lisp program to calculate the result for
> (max-cycle-length 1
> 100000000000000000000000000000000000000000000000000000) while your
> unsigned int program crashes and then feed that result as a string
> constant to an non-obfuscated C program specialized for that same sole
> input and have it run in 0.000000000000000000000000000000000000000000001
> milliseconds.
True. The lisp program will fail though if you give it an input of
something with say 10^10 zeros by running out of memory. Everything
has limits. The trick with optimization is to realize what those
limits are, and choose something with exactly as much generalization
as you need. Too little generalization, and the program will fail.
Too much, and you have something slower than optimal.
·····@vestre.net pisze:
> On 18 Apr, 11:53, camponoblanco <·············@gmail.com> wrote:
>
>> You can use memoization to speed the code.
>> Too lazy to do it now.
>>
>> http://en.wikipedia.org/wiki/Memoization
>
> It's not obvious that you can take advantage of memoization here -
> some quick tests did not give good results.
>
My test shows that simple memoization can be more than 10X faster
compared to my previous solution
One to milion range:
? (time (max-cycles 1 1000000))
(MAX-CYCLES 1 1000000) took 0 milliseconds (0.000 seconds) to run
with 2 available CPU cores.
During that period, 219 milliseconds (0.219 seconds) were spent in user mode
0 milliseconds (0.000 seconds) were spent in system
mode
31 milliseconds (0.031 seconds) was spent in GC.
4,062,064 bytes of memory allocated.
(1 1000000 525)
One to ten millions:
? (time (max-cycles 1 10000000))
(MAX-CYCLES 1 10000000) took 8,000 milliseconds (8.000 seconds) to run
with 2 available CPU cores.
During that period, 7,547 milliseconds (7.547 seconds) were spent in
user mode
15 milliseconds (0.015 seconds) were spent in
system mode
157 milliseconds (0.157 seconds) was spent in GC.
40,182,912 bytes of memory allocated.
(1 10000000 686)
And the code:
(defun get-cycles-counter ()
(let* ((*memo-boundary* 1000000)
(*memo* (make-array (1+ *memo-boundary*))))
(defun cycles** (n)
(cond
((= n 1)
1)
((and (< n *memo-boundary*) (> (aref *memo* n) 0))
(progn
(aref *memo* n)))
(t
(let* ((next (if (oddp n)
(1+ (* n 3))
(ash n -1)))
(count (1+ (cycles** next))))
; memoization
(if (< n *memo-boundary*)
(setf (aref *memo* n) count))
count))))))
(defun max-cycles (n1 n2)
(let ((cycles** (get-cycles-counter)))
(do* ((n n1 (1+ n))
(cycles (funcall cycles** n) (funcall cycles** n))
(max 1 (if (< max cycles)
cycles
max)))
((> n n2) (list n1 n2 max)))))
And if I set bigger memo buffer then for 10 000 000 I get
(time (max-cycles 1 10000000))
(MAX-CYCLES 1 10000000) took 2,000 milliseconds (2.000 seconds) to run
with 2 available CPU cores.
During that period, 2,171 milliseconds (2.171 seconds) were spent in
user mode
0 milliseconds (0.000 seconds) were spent in system
mode
203 milliseconds (0.203 seconds) was spent in GC.
47,869,192 bytes of memory allocated.
(1 10000000 686)
?
Piotr Chamera <·············@poczta.onet.pl> writes:
> ? (time (max-cycles 1 10000000))
> (MAX-CYCLES 1 10000000) took 8,000 milliseconds (8.000 seconds) to run
> with 2 available CPU cores.
> During that period, 7,547 milliseconds (7.547 seconds) were spent in
> user mode
> 15 milliseconds (0.015 seconds) were spent in
> system mode
> 157 milliseconds (0.157 seconds) was spent in GC.
> 40,182,912 bytes of memory allocated.
> (1 10000000 686)
That's still more than my na�ve implementation with lw fixnum safety
declarations:
CL-USER 2 > (time (3n+1-max-cycle-length 1 10000000))
Timing the evaluation of (3N+1-MAX-CYCLE-LENGTH 1 10000000)
User time = 6.286
System time = 0.022
Elapsed time = 6.335
Allocation = 104 bytes
3 Page faults
686
> And if I set bigger memo buffer then for 10 000 000 I get
>
> (time (max-cycles 1 10000000))
> (MAX-CYCLES 1 10000000) took 2,000 milliseconds (2.000 seconds) to run
> with 2 available CPU cores.
> During that period, 2,171 milliseconds (2.171 seconds) were spent in
> user mode
> 0 milliseconds (0.000 seconds) were spent in
> system mode
> 203 milliseconds (0.203 seconds) was spent in GC.
> 47,869,192 bytes of memory allocated.
Now that's starting to look more impressive (though I beat you on memory
allocation ;-)). (You get funny timing reports from your lisp - only
the whole seconds for the summary??)
--
(espen)
Espen Vestre pisze:
> Piotr Chamera <·············@poczta.onet.pl> writes:
>
> That's still more than my na�ve implementation with lw fixnum safety
> declarations:
I dont use fixnums declarations at all. I run it on 32 bit os and
my fixnum is to small :(
> ...
>
> Now that's starting to look more impressive (though I beat you on memory
> allocation ;-)). (You get funny timing reports from your lisp - only
> the whole seconds for the summary??)
My memoization is very naive... But it is trade - memory for speed
On Apr 18, 9:00 am, Cross <····@X.tv> wrote:
> I should have clarified that the time taken by the ace solution is less than 1
> millisecond. Target your code at that. :-)
Didn't you see the CL code posted by Raffael Cavallaro? It's been
done, next...
Francogrex wrote:
> On Apr 18, 9:00 am, Cross <····@X.tv> wrote:
>> I should have clarified that the time taken by the ace solution is less than 1
>> millisecond. Target your code at that. :-)
>
> Didn't you see the CL code posted by Raffael Cavallaro? It's been
> done, next...
That was from 1 to 100,000 not 1 to 1,000,000. Besides, the true input
file is undisclosed by UVa - Online Judge. You have to submit C, C++,
Pascal or Java code and let it be compiled and run in the server to get
your timing.
Anyway, Gambit and even Stalin Scheme compilers weren't able to get down
to the "sane" C I posted, being about 2.2-2.8 slower. Memoizing helps,
but so does for C. Declaring as fixnum doesn't help as it isn't able to
get quite the same int range as C with unsigned ints.
The fact is: the goal of high level languages is not low-level tweaking
down to machine details. They are here exactly to allow us to abstract
far away from the metal. Even if Lisp uses the same super-optimized
memoizing algorithm as C and even puts types declarations around to help
the compiler or tweak command-line parameters, that's as far as it gets.
C programmers can still use bitshifting operations, get address
references and all kind of unsafe and cryptic operations to extract
every last drop of performance from the machine.
On Sun, 19 Apr 2009 14:32:51 -0300, namekuseijin wrote:
> The fact is: the goal of high level languages is not low-level tweaking
> down to machine details. They are here exactly to allow us to abstract
> far away from the metal. Even if Lisp uses the same super-optimized
> memoizing algorithm as C and even puts types declarations around to help
> the compiler or tweak command-line parameters, that's as far as it gets.
> C programmers can still use bitshifting operations, get address
> references and all kind of unsafe and cryptic operations to extract
> every last drop of performance from the machine.
So could CL programmers -- there is nothing to prevent a CL compiler
from doing sophisticated bitwrangling, it is just not worth it most of
the time, so it is not done.
Also, even in C, these optimizations lead to obscure read-only code,
and if you leave the realm of short snippets, you will sacrifice
reliability and ease of maintenance for tiny improvements in speed.
Not worth it for most applications.
Tamas
Tamas K Papp wrote:
> On Sun, 19 Apr 2009 14:32:51 -0300, namekuseijin wrote:
>
>> The fact is: the goal of high level languages is not low-level tweaking
>> down to machine details. They are here exactly to allow us to abstract
>> far away from the metal. Even if Lisp uses the same super-optimized
>> memoizing algorithm as C and even puts types declarations around to help
>> the compiler or tweak command-line parameters, that's as far as it gets.
>> C programmers can still use bitshifting operations, get address
>> references and all kind of unsafe and cryptic operations to extract
>> every last drop of performance from the machine.
>
> So could CL programmers -- there is nothing to prevent a CL compiler
> from doing sophisticated bitwrangling, it is just not worth it most of
> the time, so it is not done.
>
> Also, even in C, these optimizations lead to obscure read-only code,
> and if you leave the realm of short snippets, you will sacrifice
> reliability and ease of maintenance for tiny improvements in speed.
> Not worth it for most applications.
Obscure write-only code. Read-only would be a blessing. ;)
On Sun, 19 Apr 2009 15:43:05 -0300, namekuseijin wrote:
> Tamas K Papp wrote:
>> On Sun, 19 Apr 2009 14:32:51 -0300, namekuseijin wrote:
>>
>>> The fact is: the goal of high level languages is not low-level
>>> tweaking down to machine details. They are here exactly to allow us
>>> to abstract far away from the metal. Even if Lisp uses the same
>>> super-optimized memoizing algorithm as C and even puts types
>>> declarations around to help the compiler or tweak command-line
>>> parameters, that's as far as it gets.
>>> C programmers can still use bitshifting operations, get address
>>> references and all kind of unsafe and cryptic operations to extract
>>> every last drop of performance from the machine.
>>
>> So could CL programmers -- there is nothing to prevent a CL compiler
>> from doing sophisticated bitwrangling, it is just not worth it most of
>> the time, so it is not done.
>>
>> Also, even in C, these optimizations lead to obscure read-only code,
>> and if you leave the realm of short snippets, you will sacrifice
>> reliability and ease of maintenance for tiny improvements in speed. Not
>> worth it for most applications.
>
> Obscure write-only code. Read-only would be a blessing. ;)
Correct, thanks :-)
On Apr 19, 1:32 pm, namekuseijin <···················@gmail.com>
wrote:
[...]
> Declaring as fixnum doesn't help as it isn't able to get quite the same
> int range as C with unsigned ints.
I tried one of the posted solutions[1] after making a single (unsigned-
byte 32) declaration under SBCL, and got a two-fold speed-up.
Declaring things to be fixnums is not the only option.
Cheers,
Pillsy
[1] Piotr Chamera's memoized solution.
namekuseijin wrote:
> That was from 1 to 100,000 not 1 to 1,000,000. Besides, the true input
> file is undisclosed by UVa - Online Judge. You have to submit C, C++,
> Pascal or Java code and let it be compiled and run in the server to get
> your timing.
>
well from 100,000 to 1,000,000, you spend more than half of the time that you
spend from 1 to 1,000,000.