BigInteger::getHighestBit() optimization(for en-/decryption)

General JUCE discussion
1

getHighestBit() is the most time-consuming (total) function while rsa-encrypting/decrypting.
I found there is much time potential in it, this code reduces the total-decryption time 35%, maybe there are also better strategies.

[code]
int BigInteger::getHighestBit() const throw()
{
/* //old
for (int i = highestBit + 1; --i >= 0;)
if ((values [bitToIndex (i)] & bitToMask (i)) != 0)
return i;
*/

for (int i = bitToIndex (highestBit + 1) ; i>=0  ; i-- )	//why highestBit + 1? why not highestBit
{
	uint32 val=values[i];
	if (val>0)												//assuming that all bits > highestBit are zero			
	{
		int s=0;
		while (val>>=1)
		{
			s++;
		}
		return s+i*32;
	}
}
return -1;

}[/code]

2

Interesting! I’d never profiled the encryption before, but that’s a nice bit of optimisation. I think it could probably be even slightly quicker using bit-shifting tricks to count the bits - I’ll have a tinker around and see what I can do. Thanks!

3

on VC++ we could even use _BitScanReverse which uses cpu instruction for finding the most significant bit

for (int i = bitToIndex (highestBit /* +1 */) ; i>=0 ; i-- ) //why highestBit + 1? why not highestBit { uint32 val=values[i]; unsigned long s; if (_BitScanReverse(&s,val)) //assuming that all bits > highestBit are zero { return (s)+i*32; } } return -1;

4

Also interesting:

http://stackoverflow.com/questions/2589096/find-most-significant-bit-left-most-that-is-set-in-a-bit-array

http://www-graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious