# Jelly, 41 bytes, language postdates challenge

```
l2Ḟ©.*×+®µ23 .*×“9®ġ’_Hµ‘_Ḟ×Ḟ2*$$µ²×³3_×H
```

Try it online!

I know this challenge was designed in the hope that golfing languages would have a hard time. In a way, they do; Jelly doesn't have any primitives for looking at the representation of a floating point number in memory. However, it's still possible to solve the challenge via working out "manually" what the representation would look like using the basic definitions of floating point arithmetic, and in fact there's some amount of mathematical interest in doing things "the hard way". Jelly's so much terser than (say) C, that the fact it has to do more work doesn't prevent the program being considerably shorter.

## Explanation

The input is a floating-point number, as a number.
In order to run the fast inverse square root algorithm, we need to find how it would be represented in memory.
Jelly doesn't have a way to do that by looking at the bit pattern, but we can do it arithmetically.

First, note that the input must be positive (or its inverse square root would be undefined). As such, it's laid out in memory as follows, from most to least significant:

- A zero bit (the sign bit, zero means nonnegative so this will always be zero);
- The exponent (dividing the number by 2 to the power of the exponent scales it into the range 1 to 2), represented in 8 bits as its value minus 127;
- The mantissa (the result of the above division), represented in 23 bits via subtracting 1, then multiplying by 2
^{23}.

The results of each of these calculations can be represented directly in Jelly. As such, we could generate the same output as C's convert-`float`

-to-`int`

memory hack does like this:

- Calculate the exponent
- Calculate the mantissa
- Take ((exponent + 127) × 2
^{23}) + (mantissa × 2^{23} - 1)

However, the last expression shown here simplifies to the following rather simpler form:

- 2
^{23} × (exponent + mantissa + 126)
- alternatively, 8388608 × (exponent + mantissa) + 1056964608 (the result of multiplying the above out)

Let's call the exponent + mantissa of the input floating point number *em* for short.
(The exponent + mantissa of a floating point number uniquely defines it.)
In other words, after the `// evil floating point bit level hacking`

comment, the C program is currently working with `i`

= 8388608 × *em* + 1056964608.

The next steps in the C program are to halve *i*, and subtract it from `0x5f3759df`

(which, in decimal, is 1597463007).
*i* is (8388608 × *em* + 1056964608); halving it gives (4194304 × *em* + 528482304); the subtraction gives (1068980703 - 4194304 × *em*).

Then, C convert this number back to a floating point number `y`

. Let's call the exponent + mantissa of `y`

*em'*.
What the C program is therefore effectively doing in the floating point representational hacking is solving the following equation:

- (1068980703 - 4194304 ×
*em*) = (8388608 × *em'* + 1056964608), which simplifies to:
- 12016095 = 4194304 ×
*em* + 8388608 × *em'*
*em'* = (12016095 - 4194304 × *em*) ÷ 8388608 = (12016095 × 2^{-23}) - *em* / 2

Now, to convert this into Jelly. We have a nice arithmetic definition of *em* and of *em'*, so we can translate it directly. First, here's how to calculate *em*:

```
l2Ḟ©.*×+®
l2 Logarithm of the input, base 2
Ḟ Round down to the integer below (produces the exponent)
© Store the exponent in a variable
.* Take (½ to the power of the exponent)
× Multiply by {the original value, by default}
+® Add the value of the variable (i.e. the exponent)
```

The original value multiplied by ½ to the power of the exponent is equal to the original value divided by 2 to the power of the exponent, i.e. the mantissa, so this is *em*.

Getting *em'* is very straightforward from here, if we want it. However, we're going to need to convert the exponent+mantissa format back into a floating point number.
This can be done unambiguously (the exponent's always an integer, the mantissa runs from 1 inclusive to 2 exclusive).
However, to extract the exponent, we're going to want to floor and subtract 1. As such, it's actually shorter to generate *em'* -1.

*em'* = (12016095 × 2^{-23}) - *em* / 2, so
*em'*-1 = (3627487 × 2^{-23}) - *em* / 2

We can encode this formula in Jelly directly:

```
µ23 .*×“9®ġ’_H
µ set this point as the new default for missing arguments
23 restart with 23
.* ½ to the power of that (i.e. 2 to the power -23)
× times
“9®ġ’ 3627487 (compressed representation)
_H minus half {the value as of the last µ command}
```

Incidentally, we need the space because `23.`

is a single token in Jelly (which evaluates to 23½).

The next step is to convert from *em'-1* to an actual floating point number `y`

. We can extract the exponent using `Ḟ`

; then the mantissa is *em'-1* + 1 - the exponent.
To produce the floating point number, we want to calculate mantissa × 2^{exponent}:

```
µ‘_Ḟ×Ḟ2*$$
µ set this point as the new default for missing arguments
‘ increment (producing em'-1 + 1)
_Ḟ subtract the exponent (producing the mantissa)
× multiply by
Ḟ2* 2 to the power of the exponent
$$ parse the previous three links as a group
```

Finally, we just need to handle the line marked `// 1st iteration`

.
This is just regular arithmetic, so encodes into Jelly really easily.
The formula is:

`y`

× (1.5 - (`x2`

× `y`

²)), where `x2`

is half the original input; this is shorter to express as
`y`

÷ 2 × (3 - (`x`

× `y`

²)), where `x`

is the original input.

And here's how it looks in Jelly:

```
µ²×³3_×H
µ set this point as the new default for missing arguments
² square
×³ multiply (×) by the original input (³)
3_ subtract (_) from 3
×H multiply by half {the value as of the last µ command}
```

## Verification

Running this program on the input `2`

produces the output `0.7069300386983334`

. This is the same value (allowing for differences in the float-to-string conversion) as produced by this VBA answer, and not equal to the mathematically correct value for 2^{-0.5}.

can you clarify what is meant by

You will get the floating point number as first argument after program name and you should implement it.? – ardnew – 2012-11-19T22:52:54.910What is

`0x5f3759df`

supposed to be in decimal? – beary605 – 2012-11-20T01:27:04.8171

@beary605: the value is discussed pretty extensively on the wikipedia article

– ardnew – 2012-11-20T02:34:57.370@ardnew: Clarified that by examples of calling the program. – Konrad Borowski – 2012-11-20T05:12:24.310

I remember this number. First time I saw this, I was amazed. Wasn't it Michael Abrash's discovery? – z0rberg's – 2016-12-31T10:31:21.103

Curious fact: Till now, the scripting language answers (Tcl, Perl, Julia) beaten all non-scripting ones! – sergiol – 2017-11-01T16:44:21.330