Find the Closest Double Palindrome

4

Given a double-precision float, find the closest double-precision float whose binary representation is a palindrome.

Input

A floating point number x. You may use any format you like for input, but the format you chose must be able to represent every possible IEEE 754 binary64 value, including denormals, distinct representations for +0 and -0, and +Inf, -Inf, and NaN.

Output

A floating point number y. You may use any format you like for output, with the same restrictions as the input format.

The Task

y is any value such that:

  • The IEEE 754 binary64 bitstring for y is a palindrome. That is, the first 32 bits are the reverse of the last 32 bits.
  • abs(x-y) is minimal by the totalOrder predicate.

Notes

  • abs(x-y) must be computed with strict IEEE 754 double-precision floating point arithmetic.
  • totalOrder puts non-numeric values and signed zeroes in this order: - NaN < -Inf < -1 < -0 < +0 < +1 < +Inf < +NaN. Otherwise it behaves like the normal < operator.
  • The rules for performing arithmetic on non-numeric values can be found at this website
  • For an overview of how binary64 floats work, see wikipedia.
  • If there is more than one value for y that satisfies the conditions, output any one of them. Note that this can only occur if abs(x-y1) == abs(x-y2), or if they are both NaN.
  • The input and output formats may be different if desired; both formats still need to obey all the rules.
  • It may be convenient to use a raw binary format for IO; this is permitted.
  • For the purposes of this challenge you may consider all NaN values as equivalent, since NaN payload behavior is implementation defined.
  • It is not sufficient to just mirror the first 32 bits. See test cases 2, 4, 5, and 7 for examples.
  • Any non-NaN double palindrome is valid output for x=+Inf or x=-Inf, since the distance is still just +Inf. Reversing the first 32 bits would not be correct though since the resulting NaN value would have a distance of +NaN > +Inf from the input.
  • A NaN though, any double palindrome would be correct.

Test Cases

Input:  0x8A2B_7C82_A27D_6D8F = -1.1173033799881615e-259
Output: 0x8A2B_7C82_413E_D451 = -1.1173031443752871e-259

Input:  0x5000_0000_0000_0001 = 2.3158417847463244e+77
Output: 0x4FFF_FFFF_FFFF_FFF2 = 2.3158417847463203e+77

Input:  0x5000_0000_0000_0002 = 2.315841784746325e+77
Output: 0x5000_0000_0000_000A = 2.315841784746329e+77

Input:  0x7FF0_0000_0000_0000 = +Inf
Output: 0x0000_0000_0000_0000 (others are possible)

Input:  0xFFF0_0000_0000_0000 = -Inf
Output: 0x0000_0000_0000_0000 (others are possible)

Input:  0x7FFC_0498_90A3_38C4 = NaN
Output: 0x0000_0000_0000_0000 (others are possible)

Input:  0x8000_0000_0000_0000 = -0
Output: 0x0000_0000_0000_0000 = +0

Input:  0x0000_0000_0000_0000 = +0
Output: 0x0000_0000_0000_0000 = +0

Input:  0x8A2B_7C82_413E_D451 = -1.1173031443752871e-259
Output: 0x8A2B_7C82_413E_D451 = -1.1173031443752871e-259

Input:  0x000F_FFFF_FFFF_FFFF = 2.225073858507201e-308
Output: 0x000F_FFFF_FFFF_F000 = 2.2250738585051777e-308

Input:  0x0000_B815_7268_FDAF = 1e-309
Output: 0x0000_B815_A81D_0000 = 1.0000044514797e-309

scoring, Standard Loopholes forbidden.

AJMansfield

Posted 2017-06-27T19:53:09.580

Reputation: 2 758

Can you please define or add a reference to IEEE 754 binary64 bitstring? – Mr. Xcoder – 2017-06-27T19:59:18.313

@Mr.Xcoder https://en.wikipedia.org/wiki/Double-precision_floating-point_format

– AJMansfield – 2017-06-27T20:00:06.490

Answers

2

C (gcc), 172 bytes

#define D double
i;D f(D x){unsigned a[]={0,0};D*A=&a;D c=0;do{for(i=0;i<32;++i){*a=*a&~(1<<i)|!!(a[1]&1<<(31-i))<<i;};c=fabs(x-*A)<fabs(x-c)?*A:c;}while(++a[1]);return c;}

(Almost) purely brute-force; takes about 24 minutes per run on my machine.

f is a function that takes a double and returns the closest palindromic double. It iterates over every palindromic 64-bit sequence (as a double), storing the closing one, and returns it at the end.

This solution uses gcc on Ubuntu 16.04 32-bit, on a little-endian 32-bit single-core Pentium 4 2.8 GHz CPU.

Explanation/Ungolfed:

int i;
double f(double x) {
    unsigned int a[]={0, 0}; // a 2-array of ints is much easier to maipulate bitwise
    double *A = &a; // than a double, so refer to the same memory
    // in two different ways, a as int[2], A as double*
    double current = 0.0;
    do {
        for(i = 0; i < 32; ++i) {
            *a = ( *a&~(1<<i) )|( (!!( (a[1]&1)<<(31-i) ))<<i);
            // reverse the bits of the second half into the first half
            // (*a is shorter than a[0])
        }
        current = fabs(x-*A)<fabs(x-current) ? *A : current;
        // if *A is closer to x than current, replace c with *A
    } while (++a[1]);
    // do-while instead of while to ensure each value is tried
    // at UINT32_MAX, overflows to 0, ending the loop.
    return current;
}

A C float (binary32) version that takes ~0.0015% as long to run (about 0.02 seconds on my machine) because it checks 1/65536 as many values: (185 179 bytes)

#define F float
i;F f(F x){unsigned short a[]={0,0};F*A=&a;F c=0;do{for(i=0;i<16;++i){*a=*a&~(1<<i)|!!(a[1]&1<<(15-i))<<i;};c=fabsf(x-*A)<fabsf(x-c)?*A:c;}while(++a[1]);return c;}

pizzapants184

Posted 2017-06-27T19:53:09.580

Reputation: 3 174