OpenEuphoria

1. Factorization

• Posted by MAP <ddhinc at ALA.NET> Mar 14, 1998
• 605 views

Here's another version of the factorization prog I wrote, it's quite
a bit faster. Also, I started another program to try to use the
bitvector scheme I posted about last time. It turned out slooow.
A major part of the bottleneck was that I was using bits_to_int()
to convert to the value I was storing. What's really needed to
get the kind of speed I want is a set of fast bit shifting funcs
that work on atoms. Has anyone out there with assembly skills
written any?
----------------------------------------------------------------------
-- factors.ex
-- Christopher D. Hickman

include get.e
without type_check

atom last_factor
function factors_recurse(atom val)
    atom r, x

    -- get 2 and 3 out of the way
    if not remainder(val, 2) then
        if val = 2 then
            return "2" -- stops the "* 1" that would occur
        end if
        return sprintf ("2 * %s", {factors_recurse(val/2)})
    end if
    if not remainder(val, 3) then
        if val = 3 then
            return "3" -- same here
        end if
        return sprintf ("3 * %s", {factors_recurse(val/3)})
    end if

    -- now uses 6n +/- 1 loop... 33% fewer tests than simple odd loop
    for cnt = last_factor to sqrt(val) by 6 do
        x = cnt
        r = remainder(val, x)
        if not r then
            last_factor = cnt
            return sprintf ("%d * %s", {x, factors_recurse(val/x)})
        end if
        x = cnt + 2
        r = remainder(val, x)
        if not r then
            last_factor = cnt
            return sprintf ("%d * %s", {x, factors_recurse(val/x)})
        end if
    end for

    -- if we made it here, it's prime
    return sprintf("%d", val)
end function

function factors(atom val)
    last_factor = 5 -- starts the loop in the right place
    return factors_recurse(val)
end function

sequence query
atom console
atom t1

query = {0,0}

while 1 do
    console = open("CON", "r")
    puts(1, "\nEnter a positive number (0 quits):")
    query = get(console)
    if query[1] = GET_SUCCESS then
        if atom(query[2]) then
            if query[2] >= 0 then
                if query[2] = 0 then
                    abort(0)
                end if
                t1 = time()
                printf(1, "\nFactors of %d = %s\n",
                      {query[2], factors(query[2])})
                printf(1, "%9.6f seconds to calculate\n",
                      time() - t1)
            end if
        end if
    end if
    close(console)
end while
----------------------------------------------------------------------
Christopher D. Hickman