For solving the problem of proportioned distribution of ads into sites at internet-scale, we had used a random number generator within a segmented number range. It was elegant and distributed synchronization and such complexities.
Any more of such elegant tricks in production software?
I've always been a fan of the Fast Inverse Square Root hack.
float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // evil floating point bit level hacking
i = 0x5f3759df - ( i >> 1 ); // what the fuck?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
return y;
}
SPITBOL/370 is a SNOBOL4 implementation for IBM mainframes. The following Dr. Dobbs articles describe some of the tricks used in the code. Elegant is the wrong word but both of these techniques are clever hacks.
For scaling view counters on the pages of popular videos Youtube increments the counter by N views with 1/N probability for each actual view. Or so I've been told.
Ad 1 has to be shown 30% of the traffic
Ad 2 has to be shown 40% of the traffic
Remaining has to be given to RTB
generate a random number between 0:100
if the number is 0-30 the Ad 1 has to be shown
if the number is 30-70 the Ad 1 has to be shown
else RTB is to be called
The servers can be now independent and no need to share the state, or have a lock based counter. For large number of requests, and with a good random number generator, you will get good results.
It might seem standard among some circles. And i have learnt them on the floor. But could never find a book or blog which describes some more examples. I was curious if others had any ideas to share.
Ah OK thanks, for somer reason I was thinking the TB in RTB was token bucket and I was scratching my head at the first letter. Now I feel silly. Cheers.
Very cool algorithm used in (among other things) redis.