Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[noodle0117]

Sorry for unclear title (not really sure how to express this idea without examples).

For a personal programming project, I'm trying to find some kind of math function/formula that reduces larger numbers by a greater amount than it reduces smaller numbers.
eg.
function(small number) -> slightly smaller number
function(big number) -> small number
function(very big number) -> small number marginally larger than function(big number)

An example would be getting the square root of a number, but sqrt tends to be computationally slow.
Getting the logarithm of a number also works, but log is even slower computationally than sqrt.

Division doesn't quite reduce larger numbers as sharply as I want.

Does anyone know any functions that can achieve this goal while remaining relatively quick to compute?

[Bauglir]

What language you using? If you have access to bitwise operations and you're working with integers you can just bitshift to the right to get log base 2 very efficiently.

I suck. That's not how it works. That divides by 2. If you bitshift until the leftmost 1 is shifted out, the number of shifts is the log base 2 (or something like it). That's less fast.

[noodle0117]

Lets just assume I'm using C++. As you said, bitshifting only divides values.

[Bauglir]

Yeah, I can't help you if you need something faster than

Code: [Select]

unsigned int log2(unsigned int input){
    unsigned int counter = 0;
    while(input){
        counter++;
        input >>= 1;
    }
    return counter;
}
You'll probably need to whip out some clever maths, if brief googling of fast square root and fast logarithm tools are any indication. Or just grab one of those.

NOTE: Above is probably terrible due to relying on a condition loop. I've never done hardcore optimization that really cares, I just know enough to know that sort of thing does not do well with pipelining and so can undercut performance. I'd wager it's slower than built in square root and logarithm functions, honestly.

[noodle0117]

This actually looks like it would work quite nicely (at least conceptually). Ty for the piece of code.