Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

/prog/ Challenge

Name: Anonymous 2007-09-04 15:06 ID:bG0CVxDp

Hey, I've stolen this challenge from some website, it's pretty easy but I know most of you will fuck it up.

A sequence is defined by:

n -> n/2 (n is even)
n -> 3n + 1 (n is odd)

Find the longest sequence, with a starting number under one million.

Bonus points when you find the solution for ten million.

Name: Anonymous 2007-09-05 9:17 ID:N3V2WcCD

>>40
I managed to get the Java one running 4.6% faster by precalculating the BigInteger values of 2 and 3 (it went from an average of 57.9s to 55.2s running time on my PC)

Apart from that, I don't know what else to check. Perhaps Python just has a more efficient arbitrary precision integer implementation than Sun's JVM.

Name: Anonymous 2007-09-05 9:38 ID:N3V2WcCD

I modified the above Python program to be equivalent to my Java one, and it has an average run time of 45.1s. Almost 20% faster - nice!

Or in other words: fuck you Java.

Name: Anonymous 2007-09-05 9:39 ID:Heaven

Someone write a Ruby version so that we can confirm that Ruby indeed is slow as fuck.

Name: Anonymous 2007-09-05 9:51 ID:Heaven

>>43
It's certainly slow as fuck to install.

Name: Anonymous 2007-09-05 10:15 ID:nfZ5LK9h

1←2←4←8←16←32←64←...
2←3←6←12←24←48←...
3←6←...
4←9←18←36←...

5 ?????
WHERE THE FUCK IS 5?????

Name: Anonymous 2007-09-05 10:15 ID:nfZ5LK9h

1←2←4←8←16←32←64←...
2←3←6←12←24←48←...
3←6←...
4←9←18←36←...

5 ?????
WHERE THE FUCK IS 5?????

Name: Anonymous 2007-09-05 10:15 ID:nfZ5LK9h

1←2←4←8←16←32←64←...
2←3←6←12←24←48←...
3←6←...
4←9←18←36←...

5 ?????
WHERE THE FUCK IS 5?????

Name: Anonymous 2007-09-05 10:16 ID:nfZ5LK9h

1←2←4←8←16←32←64←...
2←3←6←12←24←48←...
3←6←...
4←9←18←36←...

5 ?????
WHERE THE FUCK IS 5?????

Name: Anonymous 2007-09-05 10:26 ID:N3V2WcCD

>>43

Average run time is 162.9 seconds (running on same PC as Python and Java measurements from earlier)

Am I doing it wrong, or is Ruby indeed slow as fuck?

This is the first Ruby program I've ever written, so maybe I'm missing some fundamentals.

Code below:

def sequencelength(n)

  if n == 1 or n == 2 or n == 4

    len = 3

  else

    len = 1

    while n > 1

      if n%2 == 0

        n = n/2

      else

        n = 3*n + 1

      end

      len = len + 1

    end

  end

  return len

end



longestseqlen = 0



starttime = Time.now()



for n in 1..1000000

  curseqlen = sequencelength(n)

  if curseqlen > longestseqlen

    longestseqlen = curseqlen

  end

end



print "longest sequence is ",longestseqlen,"\n"

print "run time is ",Time.now()-starttime,"s\n"

Name: Anonymous 2007-09-05 10:32 ID:nfZ5LK9h

1←2←4←8←16←32←64←...
2←3←6←12←24←48←...
3←6←...
4←9←18←36←...

5 ?????
WHERE THE FUCK IS 5?????

Name: WHERE THE FUCK IS 5????? 2007-09-05 10:32 ID:nfZ5LK9h

1←2←4←8←16←32←64←...
2←3←6←12←24←48←...
3←6←...
4←9←18←36←...

5 ?????
WHERE THE FUCK IS 5?????

Name: WHERE THE FUCK IS 5????? 2007-09-05 10:33 ID:nfZ5LK9h

WHERE THE FUCK IS 5?????

Name: WHERE THE FUCK IS 5????? 2007-09-05 10:33 ID:nfZ5LK9h

WHERE THE FUCK IS 5?????

Name: WHERE THE FUCK IS 5????? 2007-09-05 10:33 ID:nfZ5LK9h

WHERE THE FUCK IS 5?????

Name: Anonymous 2007-09-05 10:33 ID:NciegGbi

WHERE THE FUCK IS SARAH CONNOR

Name: Anonymous 2007-09-05 10:38 ID:Heaven

WHERE THE FUCK IS RUBY IS SLOW AS FUCK

Name: Anonymous 2007-09-05 10:40 ID:Heaven

>>49
HAHAHA. Oh wow.

$ time ruby slow.rb > /dev/null

real    10m48.863s

user    7m36.454s

sys    0m3.721s

Name: Anonymous 2007-09-05 10:45 ID:e/Ng0Pxb

Someone needs to submit this glorious thread to programming.reddit.

Name: WHERE THE FUCK IS 5????? 2007-09-05 10:46 ID:nfZ5LK9h

WHERE THE FUCK IS 5?????

Name: Anonymous 2007-09-05 10:46 ID:Heaven

>>58
THIS IS what happens when you submit /prog/ to reddit

Name: Anonymous 2007-09-05 11:01 ID:xCbQ18id

>>58
>>60
I'm pretty sure anything from dis.4chan.org is blacklisted from reddit. It always seems to disappear pretty quickly from the new list.

Name: Anonymous 2007-09-05 11:27 ID:nfZ5LK9h

>>61
thats what happens when you submit /prog/ to reddit

Name: Anonymous 2007-09-05 11:38 ID:lmR0Mh+D

>>42
My Java prog is faster than your python one. But still, my optimized python one runs in 6 seconds.

And in C, this is even faster (under one second).

Name: Anonymous 2007-09-05 11:40 ID:N3V2WcCD

>>63
Post your Java source please.

Name: Anonymous 2007-09-05 11:40 ID:lmR0Mh+D

>>63
Also, Javas BigInteger/Decimal sucks balls, it really does.

Name: Anonymous 2007-09-05 11:43 ID:N3V2WcCD

>>65
What are you using to do arbitrary precision instead?

Name: Anonymous 2007-09-05 11:48 ID:N3V2WcCD

Oh, that optimized Python one is 4.1 seconds on my system, compared to 45.1 for the bruteforce.

Name: Anonymous 2007-09-05 11:51 ID:yKbClMxV

>>67
Source to the optimized one.

Name: Anonymous 2007-09-05 11:52 ID:yKbClMxV

>>63
Yours too.

Name: Anonymous 2007-09-05 12:02 ID:N3V2WcCD

>>68
See >>23

Name: Anonymous 2007-09-05 12:06 ID:Heaven

>>68
Oh, I didn't consider that very ``optimized''.

Name: Anonymous 2007-09-05 12:06 ID:Heaven

I meant >>69

Name: Anonymous 2007-09-05 12:07 ID:yKbClMxV

I MEANT >>70

Name: Anonymous 2007-09-05 12:15 ID:lmR0Mh+D

      int maxPosition = 0;
      int maxLength = 0;

      for (int i = 1; i < max; i++) {
      int cnt;
      long value;
      for (cnt = 1, value = i; value != 1; ++cnt) {
      if (max - value > 0 && skip[(int) value] != 0) {
      cnt += skip[(int) value];
      break;
      }
      value = 0 == (value & 1) ? value >> 1 : value + (value << 1)
      + 1;
      }
      if (cnt > maxLength) {
      maxLength = cnt;
      maxPosition = i;
      }
      skip[i] = cnt;
      }
      System.out.println("Nr: " + maxPosition);

time java XBOXITERATION
Nr: 837799

real 0m0.432s
user 0m0.360s
sys    0m0.036s

Name: Anonymous 2007-09-05 12:17 ID:yKbClMxV

>>74
How about the Python one?

Name: Anonymous 2007-09-05 12:22 ID:N3V2WcCD

>>74
Haha oh wow I'm so dense. I forgot Java had 64-bit integers. I only ended up using the BigInteger crap 'cause the 32-bit ones overflowed.

Name: Anonymous 2007-09-05 12:28 ID:lmR0Mh+D

>>76
long will overflow if you use a normal unoptimized bruteforce algorithm, also if you use the above algorithm with a limit of one million.

Name: Anonymous 2007-09-05 12:28 ID:lmR0Mh+D

>>77
#ten million

Name: Anonymous 2007-09-05 12:36 ID:N3V2WcCD

>>77
I just modified my original program to use longs and it doesn't overflow. Takes 6.0 seconds to run too.

If I add a Hashtable in to cache lengths, run time goes down to 2.5 seconds.

Name: Anonymous 2007-09-05 12:38 ID:Heaven

A NEW CHALLENGE APPEARS?

Newer Posts