7 replies to this topic

[The Crazy Phoenix]

Is there any chance I can get a method in Lua that, given a and m, returns a (mod m)?
All the function's inputs are big-endian byte tables (1 to #).
Ideally this function should be optimized as I'd be dealing with 58+ byte numbers for both inputs.
I know it'd be slow for CC, but I'm just working on a proof of concept project.

Edited by CrazyPyroEagle, 06 July 2016 - 08:12 PM.

[KingofGamesYami]

I'm pretty sure you're looking for %. Ex:

8 % 3 == 2

[The Crazy Phoenix]

 KingofGamesYami, on 06 July 2016 - 09:42 PM, said:

I'm pretty sure you're looking for %. Ex:

8 % 3 == 2

I'm not, I know % is the number modulo but due to size limitations in the Lua number, I need to use byte tables (currently big endian).

[Bomb Bloke]

Quick'n'dirty via iteration:

local numerator = {0x24, 0x03, 0xE7, 0xFF, 0x23}  -- 0d154684358435 divided into bytes, bigendian

local denominator = 24

local curRemainder = 0

for i = 1, #numerator do
	curRemainder = (numerator[i] + curRemainder * 256) % denominator
end

print(curRemainder)

Should do the job so long as your denominator isn't too large. Could be made simpler if the denominator is always a power of two.

[The Crazy Phoenix]

Unfortunately that doesn't work because, as I stated above, the modulo is also 58+ bytes in size.
I may be able to look into expanding your function into the modulo function I seek, but it's not going to be simple.

[Bomb Bloke]

Best I figure, you're going to have to do the full division, in that case. You can at least do it in base 256 to keep it relatively simple.

[The Crazy Phoenix]

I've just finished implementing a full method to do division using byte tables. Thanks for the help Bomb Bloke

local function floorDiv(a, b) -- Returns the quotient and the remainder
	local result = {}
	local current = copyTable(b)
	local values = {current}
	local lsh = 1
	while compare(a, current) > 0 do   -- Find the largest value
		print(tostring(lsh).."> "..toHexString(current))
		current = add(current, current)
		lsh = lsh + 1
		values[lsh] = current
	end
	current = copyTable(a)
	while lsh > 0 and compare(current, {0}) > 0 do
		if compare(current, values[lsh]) >= 0 then
			local index = math.floor((lsh - 1) / 8) + 1
			result[index] = bit32.bor(result[index] or 0, bit32.lshift(1, lsh - 1))
			current = subtract(current, values[lsh])
		end
		lsh = lsh - 1
	end
	return result, current
end

In case you're curious, it uses a method I manually came up with which is to perform bit-by-bit division by subtracting from the number every time it can. If it does subtract, it also sets the bit inside the result. It does this until it has checked all bits or the remainder is 0 and then returns.

Edited by CrazyPyroEagle, 08 July 2016 - 08:29 AM.

[Bomb Bloke]

Quote

Formatter keeps making my b variable uppercase and adding /> when I save changes

In the full post editor, disable emoticons.