1

I am looking for a formula that will take x and output y like so:

1        100
2        400
4        700
8        1000
16       1300
...

Essentially, for every doubling of the input, output increases by a fixed value. In this case 300, offset by 100 but that's not important. What's important is that for every doubling of the input value, i want a linear increase in output.

But there's another problem. I cannot make use of power, square roots or logarithms etc. And i can't use decimal numbers. I.E 1.512457256.... I can however use integers up to 2^31 so i can represent 1.51 as 151 / 100 and work with that in my problem. The operations i have available to me are the simple ones as well as bitwise operations:

+, -, /, * and % &, |, ^, << and >>

Or in other words, addition, subtraction, division, multiplication and modulus... As well as bitwise AND, OR, XOR, Left Shift and Right Shift.

I can also use these simple functions: max(), min() and abs()

Can this be accomplished and if so, how?

Please try and keep it simple. I have practically no skills in maths. I don't work well with "advanced" notation.

EDIT:

Note that decimal accuracy is not important. Hence, as Jaume Oliver Lafont points out below, i can check which bit is set to one in the input value and work with that as the log2(x) if need be.

But at that point, which i neglected to mention, i can use ranges and hardcode the log values as well. But i would rather avoid it if possible. However, without log2(x) i now do realize how impossible this would be. Unless there's some very intelligent approximation of log2(x) one can use.

Cadde
  • 113
  • You need a logarithmic function. Using only simple and bitwise operations, that will get complicated. Are you allowed to write a program, use loops, if statements, etc? Are you able to get the number of bits/digits of a binary number? – Dirk Jun 07 '17 at 12:25
  • @Bemte I can do limited conditional branching only. Either way, i cannot implement a logarithmic function in my environment no. And i figured as much when it struck me that i could do log2(x) to turn the exponential nature of this into a linear one. – Cadde Jun 07 '17 at 12:35

1 Answers1

2

The function is

$$f(x)=100+300\log_2(x)$$

At the points you give, $\log_2(x)$ is the position of the non-zero bit.

Can you write a log2(x) function?

Here are some ways to build such a function.

https://stackoverflow.com/questions/11376288/fast-computing-of-log2-for-64-bit-integers

Jaume Oliver Lafont
  • 5,212
  • I specifically stated i can only use a limited set of functions and operations. But i do realize that i kinda have to use log2(x) to solve this unless there's some very crude approximation i can use in it's place? – Cadde Jun 07 '17 at 12:35
  • After your edit, no i cannot write a log2(x) function. But you did mention the position of the non-zero bit which does make a lot of sense. I can use this newfound "eureka" moment for sure! – Cadde Jun 07 '17 at 12:38
  • Maybe a crude approximation you may use if accuracy is not very important can be piecewise linear approximation. Classify your number between successive powers of two and then interpolate linearly between them. – Jaume Oliver Lafont Jun 07 '17 at 12:50
  • Numbers for a segment look like this, to the left the approximation and to the right the desired value:

    $$break> for (k=0,8,print(1000+k300/8.," ",100+300log(k+8)/log(2)))$$ $$1000, 1000.000000$$ $$1037.500000, 1050.977500$$ $$1075.000000, 1096.578428$$ $$1112.500000, 1137.829486$$ $$1150.000000, 1175.488750$$ $$1187.500000, 1210.131915$$ $$1225.000000, 1242.206477$$ $$1262.500000, 1272.067179$$ $$1300.000000, 1300.000000$$

     – Jaume Oliver Lafont Jun 07 '17 at 12:55
  • I like how impossible it is to comment properly. Anyways, i will basically do log = (value & 0x8) > 0 ? 3 : ... to get the logarithm of the value and yes, i will do linear interpolation after that. Thanks! – Cadde Jun 07 '17 at 13:23