On 27/09/2013, at 12:26 AM, john skaller wrote:
> More generally this is just a standard positional number system
> with arbitrary radix in each position. For the type
>
> 3 * 5 * 7
>
> the encoding is just
>
> x * 5 * 7 + y * 7 + z
So here's the decoding rule again:
let p = x * 5 * 7 + y * 7 + z
to get the middle value:
y = p / 7 % 5
Now consider:
3 * (8 * 2 *5) * 7
To get the 2 value we do two projections:
p / 7 % 80 / 5 % 2
Now, for a sum
5 + 7 + 3
the formula is:
if case 0, s = v + 7 + 3
elif case 1, s = v + 3
elif case 2, s = v
The decode is:
if s < 3 then case 0, v=s
elif s < 7+3 then case 1 v = s - 3
else case 2 v = s - 7 - 3
This can be done in O(1) using an array lookup,
or O(log N) where N is the number of cases by a
binary chop.
To assign a component of a product is a bit tricker, but not much.
We need to save the top and bottom components.
z = p / 1 % 7
x = p / 5 / 7 % 3
and now we can just form the new tuple:
p = x * 5 * 7 + y * 7 + z
with the new y value.
It's easier for a sum, since only one of the components can
be present, we just create a new value.
So given a tuple containing tuples etc to store at a projection of projections
etc we just recurse down the applications, stripping of the projections into
a list, until we hit an lvalue (either a variable or some expression
dereferenced).
Now we process the projections bottom up by processing the list.
Now, here's some magic. First note that, there are two kinds of projections:
projections on ordinary non-compact types and projections on compact types.
For non-compact types, we can just add offsets by normal field selection.
When we hit a compact type like the one above note we can write it
3 * 8 * 2 * 5 * 7
or just
(3 * 8) * 2 * (5 * 7)
The encoding is not changed. So in particular a value fetching projection
for the 2 term can be written
p / 35 % 2
i.e. we cannot ever need more than a single division and single remainder.
If the form is an array and the index is an expression, nothing changes
except that the divisor is now the product of expressions (the remainder
term is just the "digit" size).
So similarly, to change the 2 value, we can just treat the whole thing
in a single operation (if you have multiple indices obviously they're
multiplied to form the quotient).
--
john skaller
skal...@users.sourceforge.net
http://felix-lang.org
------------------------------------------------------------------------------
October Webinars: Code for Performance
Free Intel webinars can help you accelerate application performance.
Explore tips for MPI, OpenMP, advanced profiling, and more. Get the most from
the latest Intel processors and coprocessors. See abstracts and register >
http://pubads.g.doubleclick.net/gampad/clk?id=60133471&iu=/4140/ostg.clktrk
_______________________________________________
Felix-language mailing list
Felix-language@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/felix-language
