10
\$\begingroup\$

Maybe a somewhat odd choice of language, but here is a program in ><> I have tried to optimize the execution time of. (Not golfing). The efficiency is measured in the number of required instructions on an ideal ><>-machine, which uses the same amount of time to execute each instruction.

The program does a complete factorization of a number on the stack, and prints the result. The method used is trial division of odd numbers, up to the square root of the original number. The 2-factors are calculated first. The core of this program is the third line, which wraps around, and has a minimum of 2D-program flow commands. (I have also not used p, so the source code is static, and does not modify itself.)

An online interpreter for ><> is available here.

:?!;:2%?v2n2,30.
        >:3:02.
::*$}(?v::{:@%?!v2+
;n;?=1:<
,:r~:n:02.      >:@

Here is a commented version:

:?!;                   //Checks if n is 0. Sends the next part into an infinite loop if not dealt with

    :2%?v2n2,30.           //Loop that gets all factors of 2

        >:3:02.                //Escape condition executed when the number is no longer divisible by 2, go to main loop

::*$}(?v               //Main loop, the first condition checks if the candidate for trial division is > sqrt(n)

        ::{:@%?!v2+            //Checks divisibility by modulo, if not, increase candidate by 2

;n;?=1:<               //Prints the remainder as the last factor, except when it is 1

,:r~:n:02.      >:@    //When a factor is found, it is printed, n is divided, and the program goes back to the main loop

The program outputs the numbers directly, so for testing purposes, it may be convenient to separate them with commas:

:?!;:2%?v2n2,4b*o30.
        >:3:02.
::*$}(?v::{:@%?!v2+
;n;?=1:<        
,:r~:n4b*o:02.  >:@

The main loop in detail:

The stack starts off with n,n,i ,where n is the number we are trying to factorize, and i is the iterator.

::*  //The iterator is copied two times, and mad into a square. n,n,i,s
$}   //The iterator is sent back to the bottom of the stack. i,n,n,s
(?v  //The square is compared with n. (both values are popped). If the square is larger or equal, the instructor goes down one line. i,n
::{: //n is copied two times, the iterator called to the top, and is copied too. n,n,n,i,i
@    //The three topmost values of the stack are rotated. n,n,i,n,i
%?!v //Takes the modulo of n and the iterator, if >0, the instructor jumps over the arrow down to the next line. n,n,i
2+   //Increments the iterator by two. The line wraps back to the beginning of the loop.

I would like to know if there are optimization opportunities I have missed, and if the code is fairly readable by ><> standards. Again, this is not about golfing or obfuscating the code.

If you are testing the code with the online interpretor, there is an easy way to put a number in the initial stack (Otherwise, you get the standard ><>-error "Something smells fishy...").

fish stack

\$\endgroup\$
  • \$\begingroup\$ When I paste either program into the online playground, I get "Error: Something smells fishy". Can you verify that the code actually works? \$\endgroup\$ – 200_success Apr 15 '16 at 20:05
  • 3
    \$\begingroup\$ @200_success You have to put a number in the stack first. \$\endgroup\$ – SE - stop firing the good guys Apr 15 '16 at 20:14
6
\$\begingroup\$

First off, I'd like to say that you're asking two questions which are at odds with each other. Having readable ><> code usually requires a decent amount of whitespace, but minimising the number of ticks requires reducing the amount of whitespace and a bit of golfing. I'll assume that you're primarily aiming for the latter, while keeping the code as readable as possible under this constraint.

General comments

Less than

A minor one about your explanation - ( is second < top, so by having n, s at the top of the stack you're checking whether square > n, not square >= n. If it were the latter, your code would fail for numbers like 9! (no factorial)

Floats

Just a note of warning: both the online interpreter and the official Python interpreter use floats for division, so this program would most likely fail for large numbers. Unfortunately, I don't know of any good way to perform integer division as efficiently.

Wrapping and reading direction

Wrapping the last line doesn't affect efficiency, so it's more readable to have the , follow the @. Also, if we wanted to save every tick, we could have this part on the second-last line instead:

:?!;:2%?v2n2,30.
        >:3:02.
::*$}(?v::{:@%?!v2+
       >:1=?;n; >:@,:r~:n:02.

Note that I've also flipped the :1=?;n; for readability since it fits going left-to-right.

Print if not 1

Speaking of :1=?;n;, this reads as "halt immediately if the number is 1, else print the number then halt". This could be more clearly expressed as

:1=?!n;

to "print the number if it's not 1, then halt". Alternatively, you can use -? as an idiom for "if not equals", and do

:1-?n;

to save a tick.

Division by 2 loop

It's a bit more logical to separate the initial zero check from the rest of the first line, which divides out factors of 2. This is also a bit more efficient, since we save on the 30. jump.

:?!;v
2n2,>:2%?v

Main loop efficiency

To get from the stack state [n, n, i] to [i, n, n, s], you currently do

::*}$

Instead, you can do

:}:*

Putting all of the above notes together, we get the slightly more efficient version:

:?!;v
2n2,>:2%?v
         >:3:03.
:}:*(?v::{:@%?!v2+
      >:1-?n;  >:@,:r~:n:03.

Outputting characters

This only concerns your testing code, but outputting single characters should be done with quotes for readability, i.e. ','o rather than 4b*o to output a comma.

Would-be readability comments

In terms of general ><> readability, I wouldn't call this particularly readable, but under the constraint of efficiency it's pretty good. However, if the goal were strictly readability, here are a few comments:

  • Whitespace should be used to group logical components, e.g. :2%?v 2n 2, 30..
  • It makes more sense logically to enter the main loop starting with [n, i] rather than [n, n, i].
  • Because 02. starts execution of the main loop from the second : of ::*, you have an extra : to compensate before both instances of 02.. To cut down on repetition, the main loop should be indented. (You could also move the + from the end to the start so as to not lose efficiency, but that comes at a cost to readability).

Extra: using l as a counter

For extra efficiency and sheer stupidity, we can use l (which pushes the length of the stack) as a counter to save on stack manipulation. Granted, this would run into memory problems for large numbers and is terrible for readability, but I'm sure that's the least of our worries if we're factorising in ><>!

:?!;v
2n2,>:2%?v
         >:f3.
:l:*(?v:l%?!v::
;n?-1:<     >:lnl,$~f3.
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you, this was helpful. Good to hear that there are no terrible mistakes that can make it break, or that the $O()$ is adequate. The most valuable in terms of execution time is certainly the n,n,i to i,n,n,s improvement, which saves about 6% of all ticks. Also, the more concise ways of writing a few of the fall-through branches clearly makes it more readable. Of course, I can save one more tick on each of them by making them vertical on line 3 and 5 :) \$\endgroup\$ – SE - stop firing the good guys Apr 16 '16 at 8:58
  • \$\begingroup\$ Are you serious about using "l"? That would make a huge mess of the stack... \$\endgroup\$ – SE - stop firing the good guys Apr 16 '16 at 9:08
  • \$\begingroup\$ @Hohmannfan How serious I am about l would depend on what your aim is with this piece of code. It's terrible for code maintenance, but from a theoretical point of view it completes it 10-20% fewer instructions. \$\endgroup\$ – Sp3000 Apr 16 '16 at 9:48
  • \$\begingroup\$ Also I'd like to note that if you were concerned about Big O I'd recommend using a different algorithm (e.g. a sieve), but I certainly wouldn't recommend doing that in ><> :) \$\endgroup\$ – Sp3000 Apr 16 '16 at 9:54
  • 1
    \$\begingroup\$ "I certainly wouldn't recommend doing that in ><>" is good general advise too. \$\endgroup\$ – SE - stop firing the good guys Apr 16 '16 at 10:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.