0x5f3759df and the fast inverse square root (2012)

Post by _yosefk » Tue, Oct 28, 2014, 10:03 AM UTC

sjolsen wrote: post #8

KhalilK wrote: post #2

I may be going on rampage here but " It does contain a fair bit of math " really grinds my gears! Of course it does, it is about square roots and inversions. In most of the cases, in order to optimize an algorithm or solve a problem, mathematics will do it for you, and that ranges from simple arithmetic properties to base changing theorems in linear algebra. You just can not tackle such subjects without expecting it…

Seriously, computer science itself is a branch of mathematics. Or is mathematics a branch of computer science...? It's not always weird bit-level arithmetic, but if you aren't using math at some level, you're not programming; you're just futzing around with a text editor.

Post by thewarrior » Tue, Oct 28, 2014, 11:02 AM UTC

KhalilK wrote: post #2

I may be going on rampage here but " It does contain a fair bit of math " really grinds my gears! Of course it does, it is about square roots and inversions. In most of the cases, in order to optimize an algorithm or solve a problem, mathematics will do it for you, and that ranges from simple arithmetic properties to base changing theorems in linear algebra. You just can not tackle such subjects without expecting it…

Post by simias » Tue, Oct 28, 2014, 11:10 AM UTC

Post by readerrrr » Tue, Oct 28, 2014, 11:19 AM UTC

spiritplumber wrote: post #3

If anyone wants a fast atan2 that I wrote a while ago (2007), for making a microcontroller navigate, it's at http://robots-everywhere.com/portfolio/math/

Post by kaoD » Tue, Oct 28, 2014, 11:34 AM UTC

mkesper wrote: post #16

thewarrior wrote: post #14

Tl;DR : The fast inverse square root is based on the fact that the integer representation of a floating point number is a rough approximation of its logarithm. So convert floating point to its integer representation. So now you have its approximate logarithm. Now take half of that and improve that with some Newton raphson.

So convert floating point to its integer representation. Would something dirty like this be feasible in rust?

    fn fast_inv_sqrt(x: f32) -> f32 {
        let f: f32 = unsafe {
            let i: i32 = std::mem::transmute(x);
            std::mem::transmute(0x5f3759df - (i >> 1))
        };
        f * (1.5 - 0.5 * x * f * f)
    }

    println!("{}", fast_inv_sqrt(1.0));
      //=> 0.998307
    println!("{}", fast_inv_sqrt(255.0));
      //=> 0.062517