Complete factorization in ><>

Question

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...").

Answer 1

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.