Subnostr

you shouldn’t be interpreting it as an integer either way and instead decode it to bits word by word

it's a simpler implementation, the implementation is not material to the encoding except for that first word and 1 bit out of 8 for a simpler encoding that runs an iterative word-wise division and multiplication series is simpler shorter code

i thought about drawing 256 bits in a line and creating a scheme to encode the bitshifts required for each group of bytes but - it's just more complex and error prone, it will be a longer piece of code compared to a big integer division and multiplication function

mainly, it requires a another table, which i estimate would be about 96 bytes long to hard-encode all the decisions required to do it by bit shifting

because our divisor is a power of two, the CPU is also optimizing this heavily as it knows that it's a shift of 11 in either direction

Reply to this note

Please Login to reply.

Discussion

ᴛʜᴇ ᴅᴇᴀᴛʜ ᴏꜰ ᴍʟᴇᴋᴜ 1y ago

because our bit-size is a power of to, 2^11, the CPU can optimize the operation as bit shifts along 64 or 32 bit wide segments of the number anyway, it is a false economy using a table of bitshifts, you can do it this way destructively, just like in my algorithm

the big number integer math library does not do anything complex for this operation, it's shift and overflow/underflow, because it's a power of 2

ᴛʜᴇ ᴅᴇᴀᴛʜ ᴏꜰ ᴍʟᴇᴋᴜ 1y ago

also, btw, if you switch it over to arrays of 64 bit words the operation is easy to see how fast it actually will be run by the - each 11 bit division round is done by shifting 5 64 bit words right (from right to left