What's the best way to do base36 arithmetic in perl?
- by DVK
What's the best way to do base36 arithmetic in Perl?
To be more specific, I need to be able to do the following:
Operate on positive N-digit numbers in base 36 (e.g. digits are 0-9 A-Z)
N is finite, say 9
Provide basic arithmetic, at the very least the following 3:
Addition (A+B)
Subtraction (A-B)
Whole division, e.g. floor(A/B).
Strictly speaking, I don't really need a base10 conversion ability - the numbers will 100% of time be in base36. So I'm quite OK if the solution does NOT implement conversion from base36 back to base10 and vice versa.
I don't much care whether the solution is brute-force "convert to base 10 and back" or converting to binary, or some more elegant approach "natively" performing baseN operations (as stated above, to/from base10 conversion is not a requirement). My only 3 considerations are:
It fits the minimum specifications above
It's "standard". Currently we're using and old homegrown module based on base10 conversion done by hand that is buggy and sucks.
I'd much rather replace that with some commonly used CPAN solution instead of re-writing my own bicycle from scratch, but I'm perfectly capable of building it if no better standard possibility exists.
It must be fast-ish (though not lightning fast). Something that takes 1 second to sum up 2 9-digit base36 numbers is worse than anything I can roll on my own :)
P.S. Just to provide some context in case people decide to solve my XY problem for me in addition to answering the technical question above :)
We have a fairly large tree (stored in DB as a bunch of edges), and we need to superimpose order on a subset of that tree. The tree dimentions are big both depth- and breadth- wise. The tree is VERY actively updated (inserts and deletes and branch moves).
This is currently done by having a second table with 3 columns: parent_vertex, child_vertex, local_order, where local_order is an 9-character string built of A-Z0-9 (e.g. base 36 number).
Additional considerations:
It is required that the local order is unique per child (and obviously unique per parent),
Any complete re-ordering of a parent is somewhat expensive, and thus the implementation is to try and assign - for a parent with X children - the orders which are somewhat evenly distributed between 0 and 36**10-1, so that almost no tree inserts result in a full re-ordering.