kokke / kokke/tiny-bignum-c

Optimization proposal for divisions

Open
#12 4 comments 2 reactions 0 assignees View on GitHub
Dominant language
C
Stars
474
Forks
90
PR merge metrics
No merged PRs in 30d

Description

The current division algorithm uses a [BIGNUM structure for 'current'](https://github.com/kokke/tiny-bignum-c/blob/e814d2b6b522ecaa67701453c492811a8adbc555/bn.c#L282) while its task can be completed with natural integer arithmetics. In my local fork (sorry, it's still a hot mess), I have changed the algorithm as follows, where several names and small things have been altered, but should still be recognizable fine:
```
//
// Use an integer of natural size to store the current Bit index as 'current'
// is always a 2's potency. While a BIGNUM can theoretically hold a
// 2's potency eight times larger than what can represent as Bit index with a
// natural integer (Bytes vs Bits), this cannot happen within this function
// as 'a' aligned to the next 2's potency would need to be just as big for
// this to be the case. This cannot happen due to the address space
// limitation.
//
size_t currentBitIndex = 0; // int current = 1;
bignum_u_assign_const(denom, b); // denom = b
bignum_u_assign_const(tmp, a); // tmp = a

const DTYPE half_max = 1 + (DTYPE)(((1ULL << (8 * WORD_SIZE)) - 1U) / 2);
bool overflow = false;
while (bignum_u_cmp(denom, a) != LARGER) // while (denom <= a) {
{
if (denom->d[BN_U_DLEN(denom) - 1] >= half_max)
{
overflow = true;
break;
}
++currentBitIndex; // current <<= 1;
_lshift_bit_const(denom, 1); // denom <<= 1;
}
if (!overflow)
{
_rshift_bit_const(denom, 1); // denom >>= 1;
--currentBitIndex; // current >>= 1;
}
bignum_u_init_const(c); // int answer = 0;
//
// currentBitIndex cannot add-wraparound to reach this value as reasoned in
// the comment before.
//
while(currentBitIndex != (size_t)0U - 1U) // while (current != 0)
{
if (bignum_u_cmp(tmp, denom) != SMALLER) // if (dividend >= denom)
{
bignum_u_sub(tmp, denom, tmp); // dividend -= denom;
bignum_u_or_int (c, 1, currentBitIndex); // answer |= current;
}
--currentBitIndex; // current >>= 1;
_rshift_bit_const(denom, 1); // denom >>= 1;
}
```
Along with this newly introduced function:
```
void bignum_u_or_int(ubn* a, DTYPE v, size_t nbits)
{
require(a, "a is null");

const uint8_t nbits_pr_word = (WORD_SIZE * 8);
size_t nwords = nbits / nbits_pr_word;
uint8_t nwordbits = nbits % nbits_pr_word;

if (nwords >= BN_U_DLEN (a)) {
return;
}

a->d[nwords] |= (v << nwordbits);
}
```
BN_U_DLEN returns the array size of the current sturcture instance, which I added because I cannot affort having every BIGNUM at the maximum required size among all.

This new function is also a really important one performance-wise for different tasks as it allows super-fast construction of 2's potencies. For example, I also used it for the calculation of R², used for Montgomery arithmetics, where R is a 2's potency. The BoringSSL algorithm utilizes BIGNUM shift, pow and mul algorithms for its construction, when with this function, it can be achieved easily with just a preceeding BIGNUM init.

Contributor guide

No contributing guide indexed for this repository

Research direction

Read bn.c around the division algorithm linked in the issue, then trace BN_U_DLEN and the proposed bignum_u_or_int API. Compare the proposed division changes with the existing BIGNUM representation and review its stated use in R² Montgomery arithmetic; done means the optimization is integrated without breaking those operations.

Written by the indexing model from the issue text.

Assessment

Tech stack
c
Domain
tooling
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.