20
\$\begingroup\$

This is different from Floating Point XOR, and more in the spirit of a comment by R.. GitHub STOP HELPING ICE on that challenge, but I thought of this idea independently.

Generalized XOR

The bitwise exclusive or (XOR) operation is usually considered in terms of integers, but it can be naturally generalized (extended, in fact!) to real numbers. There are some finicky details when asking which representation to choose for finite expansions, but to simplify matters, we will only use binary floats. For example, 3.141592653589793 ^ 0.2 is

3.141592653589793: 11.001001000011111101101010100010001000010110100011000
0.200000000000000: 00.0011001100110011001100110011001100110011001100110011010
                   11.000101110000110001011001101110111011011010010000010...
                       ≈ 3.090032203987506

The values were written out exactly and a bitwise XOR performed. Note that the result is not always exactly representable as a double, but we can round.

Challenge

Given two positive (IEEE-754) double-precision floating-point numbers, find their XOR as numbers. The answer must have a relative accuracy of 1e-6, i.e., the error should be at most 1e-6 times the correct answer. (The error bound is there because the result is not always exactly representable.)

Examples (rounded to within 1 ulp—answers may vary):

1 ^ 2 -> 3
3.141592653589793 ^ 2.141592653589793 -> 1
2.718281828459045 ^ 2.141592653589793 -> 0.5776097723422073  (funnily close to the Euler–Mascheroni constant)
1000000000 ^ 0.1 -> 1000000000.1
0.002 ^ 0.0016666666666666668 -> 0.0036340002590589515
0.002000000000000001 ^ 0.002 -> 8.6736173798840355e-19
1e+300 ^ 1 -> 1e+300
1e+300 ^ 4e299 -> 1.2730472723278628e+300
0.1 ^ 0.1 -> 0
7.888609052210118e-31 ^ 5.380186160021159e-32 -> 8.426627668212235e-31

Notes

Subnormal numbers (1), nonpositive numbers, and non-finite numbers do not need to be supported, but it should output zero when the operands are equal. Standard loopholes are of course not allowed, and the inputs may be given in any format corresponding closely to a float (decimal, 64-bit integer bit representation, etc.). This is a code golf question; may the shortest answer win.

\$\endgroup\$
16
  • \$\begingroup\$ Maybe you should first post this inside the Sandbox, codegolf.meta.stackexchange.com/questions/2140/… In case your question has problems. \$\endgroup\$ May 12 at 3:30
  • 1
    \$\begingroup\$ Oh interesting, didn't know there was a sandbox. Well, hopefully the question is clear enough. \$\endgroup\$ May 12 at 3:40
  • 1
    \$\begingroup\$ Related challenge for rational numbers \$\endgroup\$
    – alephalpha
    May 12 at 3:45
  • 6
    \$\begingroup\$ @NumberBasher actually, when creating a new question, it says to first put them in the sandbox: "Please follow a standard template and post first in the meta Sandbox for feedback." \$\endgroup\$
    – Steffan
    May 12 at 3:55
  • 1
    \$\begingroup\$ Well, probably deterministic is a better word than exact, but I got your point. I initially felt a bit weird to specify a decimal error range to such operation. \$\endgroup\$
    – xiver77
    May 12 at 4:36

13 Answers 13

9
\$\begingroup\$

JavaScript, 47 bytes

f=(x,y,k=8**341)=>k&&k*(x<k^y<k)+f(x%k,y%k,k/2)

Try it online!

k runs through every representable power of 2 and adds it to the result, or not, as appropriate.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I love this one! \$\endgroup\$ May 12 at 19:02
4
\$\begingroup\$

Wolfram Language (Mathematica), 58 bytes

Plus@@Apply@Xor//@{0,(i=#2;2^--i#&/@#)&@@@#~RealDigits~2}&

Try it online!

Input two Reals in a list. Also works with an arbitrary even number of Real arguments.

\$\endgroup\$
4
\$\begingroup\$

C (gcc), 250 234 bytes

double f(double x,double y){long m,o,a,c,b,d;if(x<y){double z=x;x=y;y=z;}m=-1lu>>12;o=1l<<52;a=*(long*)&x;b=*(long*)&y;c=a>>52;d=b>>52;a=(a&m|o)^(b&m|o)>>(c-d<53?c-d:53);b=__builtin_clzl(a)-11;a=a?a<<b&m|c-b<<52:0;return*(double*)&a;}

Try it online!

I thought directly manipulating the bit representation would be the shortcut, but it wasn't..

A bit ungolfed,

double f(double x, double y) {
  long m, o, a, c, b, d;
  if (x < y) {
    double z = x;
    x = y;
    y = z;
  }
  m = -1lu >> 12;
  o = 1l << 52;
  a = *(long *)&x;
  b = *(long *)&y;
  c = a >> 52;
  d = b >> 52;
  a = (a & m | o) ^ (b & m | o) >> (c - d < 53 ? c - d : 53);
  b = __builtin_clzl(a) - 11;
  a = a ? a << b & m | c - b << 52 : 0;
  return *(double *)&a;
}
\$\endgroup\$
9
  • \$\begingroup\$ Maybe in assembly language, right-shift one mantissa by e1-e2 (difference of the exponent fields). The precision requirements are far from 1ulp, let alone a 0.5ulp correctly-rounded result. x86 SIMD shifts saturate the shift count, so that would shift all the bits out if one double was much smaller magnitude than the other. Oh wait, we need to sort them first so we're right-shifting the smaller-magnitude one. Hrm, AVX-512 has a vpmaxuq / vpminuq. And oh crap, there's the implicit 1 bit in the mantissa. x87 80-bit floats where that's explicit, maybe... \$\endgroup\$ May 12 at 18:14
  • \$\begingroup\$ It's probably a lot easier with arbitrary-precision ints, but this is lovely. \$\endgroup\$ May 12 at 19:06
  • \$\begingroup\$ @PeterCordes: Indeed, I was thinking there could be a funky asm solution (couldn't come up with one off the top of my head). \$\endgroup\$ May 12 at 19:06
  • \$\begingroup\$ @OvinusReal: I got around to trying this, but 80-bit x87 doesn't solve everything; it still requires manual normalization. fld tword [rdi] can get a non-normalized 80-bit float into an x87 register (after 3.14... ^ 2.14... gives <invalid float> (raw 0x40004000000000000000)), but adding 0.0 to it produces a -nan. Apparently the 80287 FPU supported "unnormal" numbers where the explicit leading 1 of the mantissa was zero, but it doesn't have SSE or MMX for saturating shift counts. (Or 64-bit int shifts). \$\endgroup\$ May 13 at 2:36
  • \$\begingroup\$ @OvinusReal: If anyone wants to play around some more, godbolt.org/z/bP9sKefnP is my (dis)proof of concept, with design notes on the showstopper bug. Manual renormalization can work with lzcnt / shl mantissa / add exponent, although a zero mantissa is still a special case (need to zero the exponent). At least cancellation of leading 1s is only possible if the shift count was zero, i.e. equal exponents, so none of the bits shifted out need to become significant. \$\endgroup\$ May 13 at 3:00
4
\$\begingroup\$

C (gcc), 202 196 bytes

-6 bytes thanks to @ceilingcat

double a,b,t;long*c=&a,*d=&b,r,e,m=1L<<52;main(){scanf("%lf%lf",c,d);b>a?t=a,a=b,b=t:0;for(r=(*c&m-1|m)^(*d&m-1|m)>>(*c>>52)-(*d>>52),e=*c&m*4095;*c^*d&&!(r&m);r+=r)e-=m;*c=e|r&~m;printf("%f",a);}

Try it online!

What the program basically does:

  • save two doubles from stdin into variables a and b; if needed, swap the two doubles so a>b always;
  • take the exponent of a as the exponent of the result;
  • take the fraction parts of a and b, the leading implicit bit, left shift b (according to the exponents difference), and XOR the two values to obtain the fraction of the result;
  • finally, in the result if there are leading zeros in the fraction, remove them (and decrement the exponent).
\$\endgroup\$
0
4
\$\begingroup\$

x86-64 machine code, x32 ABI, 64 58 55 54 53 49 48 46 44 bytes

xxd output:

00000000: 87fc 5859 5e5a 6629 d17d 0548 96f7 d9eb  ..XY^Zf).}.H....
00000010: 01ca 6683 f940 7d0f 48d3 ee48 31f0 87d1  ..f..@}.H..H1...
00000020: 7805 48d1 e0e2 f951 5089 fcc3            x.H....QP...

In assembly, with comments:

xor_double:
    xchg esp,edi # save stack pointer and points new stack at the input

    # long doubles are 80-bit floating point numbers,
    # with the low 8 bytes giving the significand and the high 2 bytes giving the exponent
    # Conveniently, long doubles have an alignment of sixteen, so the "stack" now looks like:
    #  rsp    --> significand of first argument 
    #  rsp+8  --> exponent of first argument (plus six bytes of junk)
    #  rsp+10 --> significand of second argument 
    #  rsp+18 --> exponent of second argument (plus six bytes of junk)
    # So, just 4 pops puts all the arguments into registers:

    pop rax # rax=sig1
    pop rcx # rcx=junk48:exp1
    pop rsi # rsi=sig2
    pop rdx # rdx=junk48:exp2

    # check which argument is greater and swap the two if the second is greater. Otherwise swap them

    sub cx,dx   # find difference of exponents
    jge good    # jmp if exp1 >= exp2

    # exp1 < exp2, switch around the arguments

    xchg rsi,rax
    neg ecx

    # note that dx is unchanged and is now the biggest exponent- this will also be true in the other branch

    # This next two opcodes assemble together to EB 01 CA. If decoded from here, that is "JMP $+1 ; .byte CA", which skips the CA byte
    # But the "jge good" earlier jumps to the middle of EB 01 and so it is instead decoded as "01 CA", or "add edx,ecx"
    .byte 0xEB  
good:
    add edx,ecx
    # dx=cx-dx+dx=original value of cx, the biggest exponent

switched:
    cmp cx,0x40 #ratio >= 2**64, just return initial number
    jge dontxor
    shr rsi,cl  #shift the smaller significand so they line up
    xor rax,rsi
    
    # the significand of a floating point number always has 1 as its MSB.
    # so if it's missing, shift the bits around to restore it
    # i.e. multiply significand by two and subtract one off the exponent until the MSB is 1

    xchg ecx,edx
subnormal_loop: #multiply significand by two and subtract exponent by 1 until either exponent is zero or the number is normal
    js dontxor #done
    shl rax
    loop subnormal_loop #decrements ecx and jmp if not zero

dontxor:
    # return output in long_double[1]
    # put exponent in place
    push rcx
    # put significand in place
    push rax
    # restore the stack pointer
    mov esp,edi
    ret

Takes a pointer to an array of 80-bit x87 long doubles and returns in the 2nd element of the array. Uses the x32 ABI (not to be confused with x86-32), which is just like the usual System V ABI, but all pointers are 32 bits.

The padding outside the actual 10-byte long doubles is allowed to be garbage, not zero, which means we have to be careful when comparing or using FLAGS results from operations on exponents: 16-bit operand-size is necessary because we loaded the whole qword including high garbage into the full register.

Because it uses the x32 calling convention, you can compile this and link it with a C program to test it, with the function prototype void xor_double(long double[2]). You will need to compile it as x32, though.

The strategy is to shift the smaller number's significand to the right, by the difference in exponent. This aligns the significand to the place-value position of the significand of the larger, like they were fixed-point. (This may mean shifting out all the bits if the exponents are different by 64 or more, but x86 scalar shifts mask the count by &63 or &31 so we need to special-case that).

Then xor the aligned significands and use this as the 64-bit significand with the larger exponent.

80-bit long double has an explicit leading 1 in the 64-bit significand, unlike 64-bit double (IEEE binary64) using an implicit 1 (implied by a non-zero exponent field). That means shift/xor Just Works on the significand field directly.

But we still need to renormalize when equal exponents cause the leading 1 bits cancel between significands. Other than subnormals (where the exponent field is zero), long double values with bit 63 clear are not valid. (8087 and 80287 allow them as "unnormal" according to Wikipedia, but hardware operations on such a value on 387 and later treat them as invalid, producing NaN. All x86-64 CPUs include 387-compatible FPUs, and we need 64-bit mode to make it convenient to deal with a 64-bit significand.)

The renormalization uses a loop command, which decrements the exponent and jumps back to the start of the loop. This is necessary because if the significand is zero, the exponent must also be cleared or the result is an invalid floating point number. This actually clears rcx in that case, not just cx, which potentially makes the program take (much) longer, but is harmless otherwise.

The renormalization loop also handles the case of two equal inputs, where xoring aligned significands leaves zero. We shift left (and decrement the exponent) until a 1 bit appears at the top of the significand (normal case), or the exponent field becomes zero. (Producing a subnormal or a zero).

This handles the equal-input case because left-shifting an all-zero significand will never shift a 1 to the top, so eventually the exponent becomes zero. If there is a 1 bit somewhere but the exponent becomes zero before it gets to the top, in that case it is a valid subnormal value. (Too small to be representable as a normalized float.) The question doesn't require us to support subnormal inputs or outputs so the actual correct value isn't required in this case, although it probably is correct. This ended up being shorter than lzcnt / shl plus branching for special cases.

At the end, it returns a long double*, which "conveniently" points to [rsp] right after the function call. Returning a pointer into the calling function's stack frame is perhaps somewhat malicious compliance with the calling conventions, but it works!

Some general notes on registers:

  • I avoid rbx, rbp, and rsp as registers because the System V ABI forbids changing them without saving their previous value, which costs some bytes.
  • I avoid r8-r15 because they cost an extra byte for most uses.
  • In most cases using a 32-bit register saves some bytes, so I only use cx and dx when the junk in the higher bits of the registers would get in the way.
  • Using rax instead of any other register for one of the significands saves a byte on xchg, since xchg rax,[anything] is two bytes instead of three.
  • ecx has many special uses. It is the only register allowed for shr [reg],cl, and rcx is the only one used by loop. That is why the xchg ecx,edx is required to put the exponent in this special register.

Try it online! Note that TIO doesn't appear to support the x32 ABI, so I simulated it by using mmap to create a new stack at a 32 bit address.

\$\endgroup\$
39
  • \$\begingroup\$ For the calling convention, taking a pointer in RDI (long double vals[2]) would let you avoid a SIB byte on every [RSP + disp0/disp8] addressing mode, like I was planning in an attempt I was playing with. And you could say it updates the first array element to be the xor, unless it's more convenient to return in x87; looks like maybe yes for the equal-exponent case. \$\endgroup\$ May 13 at 10:06
  • \$\begingroup\$ You could also define a custom ABI where the padding above the 80-bit floats has to be zero, so you can use dword mov instead of movzx. And/or you could use mov [args+0x10], edx to store the new exponent field, writing part of the padding. You still have call-clobbered RSI free to avoid call-preserved RBX, to be closer to x86-64 SysV (or following it exactly). \$\endgroup\$ May 13 at 10:13
  • \$\begingroup\$ Also, isn't not cx/inc ecx equivalent to neg cx, except for clobbering FLAGS which you aren't still using? This could use comments, I'm not sure exactly why you want to leave the high bits set in ECX. I think you only use the low byte of the negated result, so neg cl would be shorter, having its own opcode instead of a prefix byte for neg cx. \$\endgroup\$ May 13 at 10:14
  • 1
    \$\begingroup\$ @PeterCordes Yes, I did mean fild. And I needed to subtract 0x403E to get the exponent right, to unbias it and shift the radix point. Anyway I ended up figuring out how to just fix the subnormal floats manually so I removed fscale in the end. The only special case still left in is for a==b. \$\endgroup\$
    – Chris
    May 13 at 20:54
  • 1
    \$\begingroup\$ It'd be nice to get rid of jmp switched, but we do seem to need an if/else to get the higher exponent into a known place. Nice trick with adding the negated value. We can effectively skip the 2-byte 01 xx add instruction with 1 byte instead of a full 2-byte jmp rel8, though: see Tips for golfing in x86/x64 machine code - use .byte 0xEB, the opcode for a jmp re8, to consume the 01 add opcode as a rel8, jumping over the ModRM (to the switched label). In the hexdump, this is replacing eb 02 01 ca with eb 01 ca. \$\endgroup\$ May 14 at 0:23
3
\$\begingroup\$

Charcoal, 45 bytes

F²⊞υN≔X²⁺φ²³η≔⁰ζW⌈υ«F﹪ΣEυ‹κη²≧⁺ηζ≧﹪ηυ≧∕²η»⭆¹ζ

Try it online! Link is to verbose version of code. Note: Charcoal requires floating-point numbers to contain a ., which is why the link uses 1.0e+300 as the first input. Explanation:

F²⊞υN

Input the two numbers.

≔X²⁺φ²³η

Start at 2¹⁰²³.

≔⁰ζ

Start with a zero result.

W⌈υ«

Repeat until the inputs are zero.

F﹪ΣEυ‹κη²

If exactly one of the inputs is less than the power of 2, then...

≧⁺ηζ

... add that power of 2 to the total.

≧﹪ηυ

Subtract the power of 2 from those inputs that are not lower.

≧∕²η

Halve the power of 2. (Sadly I can't use Halve here because it rounds the result for some inexplicable reason.)

»⭆¹ζ

Format the result as a float. (Charcoal defaults to formatting large floats as an integer.)

\$\endgroup\$
3
\$\begingroup\$

Swift Language, 113 bytes

typealias D=Double;let c=D(bitPattern:1<<32);let x:(D,D)->D={D(bitPattern:($0*c).bitPattern^($1*c).bitPattern)/c}

Try it online!

Based on the 87 byte GCC answer. Unfortunately swift's verbosity gets in the way of brevity when bitcasting

\$\endgroup\$
1
  • \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ May 13 at 2:26
3
\$\begingroup\$

Python 3, 57 bytes

f=lambda a,b,e=8**341:e and(a//e+b//e)%2*e+f(a%e,b%e,e/2)

Try it online!

\$\endgroup\$
4
  • 3
    \$\begingroup\$ You're incorrectly assuming that scaling up by 2^64 will put all the significant bits into the integer part. The exponent range of a double goes down to 2^{-1022} (about 10^-308) for normalized values, still with 53 significant mantissa bits. en.wikipedia.org/wiki/Double-precision_floating-point_format. Your answer incorrectly gives 0.00 for an input of (1.2e-20, 1.5e-20), but works for (1.2e-20 * 2**40, 1.5e-20 * 2**40) (same mantissa bits, larger exponents). \$\endgroup\$ May 12 at 17:29
  • 2
    \$\begingroup\$ It's not this simple; a large multiplier to allow tiny values will make it fail for non-tiny values since Python only has arbitrary-precision integers, not arbitrary-precision doubles. It's not that Python converts floats above 1e308 to inf, it's that such floats don't exist as IEEE binary64. Your multiplication overflows for that test case, and IEEE math saturates to +Inf on overflow. So it's not an implementation limit, it's an algorithm problem: IEEE FP multiplication isn't safely usable the way you want. Part of the challenge of this problem is handling test cases close to DBL_MAX. \$\endgroup\$ May 12 at 17:32
  • 1
    \$\begingroup\$ TL:DR: for any chosen multiplier, it works for about half the exponent range of IEEE binary64 double-precision FP inputs. The size of the multiplier determines which slice you take; this one includes more large number than small numbers. \$\endgroup\$ May 12 at 18:07
  • 1
    \$\begingroup\$ @PeterCordes Good point, fixed. \$\endgroup\$
    – Jitse
    May 13 at 6:22
3
\$\begingroup\$

Assembly (gcc, x64, Linux), custom ABI, 39 37 bytes

xxd dump:

00000000: 5f58 595e 5a29 d17d 0548 96f7 d9eb 01ca  _XY^Z).}.H......
00000010: e305 48d1 eee2 f948 31f0 87d1 7805 48d1  ..H....H1...x.H.
00000020: e0e2 f957 c3                             ...W.

Uses the System V ABI, but returns long doubles in cx:rax, high bits of variables passed on the stack must be zeroed, and rsp is decremented by 0x20 per call.

xor_double:

    # Custom ABI: like System V but returns long doubles in cx:rax, zeroes out high bits of stack variables, and decreases rsp by 0x20

    # System V passes long doubles on the stack. long doubles are 80-bit floating point numbers,
    # with the low 8 bytes giving the significand and the high 2 bytes giving the exponent
    # Conveniently, long doubles have an alignment of sixteen, so the stack looks like
    #  rsp    --> return address
    #  rsp+8  --> significand of first argument (plus six bytes of zeroes)
    #  rsp+10 --> exponent of first argument
    #  rsp+18 --> significand of second argument (plus six bytes of zeroes)
    #  rsp+20 --> exponent of second argument
    # So, just 5 pops puts all the arguments into registers:

    pop rdi # rdi=return address
    pop rax # rax=sig1
    pop rcx # rcx=0:exp1
    pop rsi # rsi=sig2
    pop rdx # rdx=0:exp2

    # check which argument is greater and swap the two if the second is greater. Otherwise swap them

    sub ecx,edx   # find difference of exponents
    jge good      # jmp if exp1 >= exp2

    # exp1 < exp2, switch around the arguments

    xchg rsi,rax
    neg ecx

    # note that edx is unchanged and is now the biggest exponent- this will also be true in the other branch

    # This next two opcodes assemble together to EB 01 CA. If decoded from here, that is "JMP $+1 ; .byte CA", which skips the CA byte
    # But the "jge good" earlier jumps to the middle of EB 01 and so it is instead decoded as "01 CA", or "add edx,ecx"
    .byte 0xEB  
good:
    add edx,ecx
    # dx=cx-dx+dx=original value of cx, the biggest exponent

switched:
    jrcxz equal
    shr rsi #shift the smaller significand so they line up
    loop switched
equal:
    xor rax,rsi

    # the significand of a floating point number always has 1 as its MSB.
    # so if it's missing, shift the bits around to restore it
    # i.e. multiply significand by two and subtract one off the exponent until the MSB is 1
    
    xchg ecx,edx
subnormal_loop: #multiply significand by two and subtract exponent by 1 until either exponent is zero or the number is normal
    js done #not subnormal
    shl rax
    loop subnormal_loop

done:
    push rdi #push return address
    ret

Try it online!

The overall strategy is similar to my other answer, and most of @PeterCordes's very helpful contribution still applies. This answer saves:

  • two bytes by avoiding otherwise useless pushes at the end (and thus decrements rsp by two). This also makes a loop strategy jrcxz; shr rsi; loop shorter than cmp cx,0x40; jge; shr rsi,cl. I can't use that in the first answer because it depends on rcx, which is full of junk.
  • one byte every time ecx or edx is used instead of cx (which can only be done by insuring that the higher bits are set to zero in the function call).
  • five bytes by returning in rax:rdx instead of the x87 stack, which removes the need to push the result back on the stack and use fld tbyte ptr [rsp] to load it into the x87 stack.
\$\endgroup\$
4
  • \$\begingroup\$ Nice, yeah worth a separate answer to get this creative with the ABI allowing different strategies. xchg ecx,edx might as well be mov ecx,edx; only xchg-with-accumulator saves a byte. Doesn't this actually return in CX:RAX? (By convention the high part is listed first, just like left-to-right place-value in a multi-digit number). If you wanted to return in DX:RAX, you could use dec edx / jnz instead of mov + loop. Except that doesn't work because js next iteration needs to read FLAGS from shr this iteration, and only loop loops without clobbering FLAGS. \$\endgroup\$ May 17 at 4:09
  • \$\begingroup\$ @PeterCordes Thanks! It returned in dx:rax before I figured out how to get loop to work and I missed one of the two places it was mentioned. The order was a mistake. My brain is still big-endian. ;) \$\endgroup\$
    – Chris
    May 17 at 4:15
  • \$\begingroup\$ BTW, the number you're renormalizing is a "denormal", but usually not a sub-normal. A denormal is any float where the leading digit of the significand isn't 1. A subnormal is the special case of that where the exponent field is all zero (so the value can't be represented as a normalized float.) The only denormals the FPU will ever generate on its own are subnormals, so many prefer that more specific term. Except apparently on 287 and earlier where they called it an "unnormal" (en.wikipedia.org/wiki/…) and it indicated precision loss. \$\endgroup\$ May 17 at 4:16
  • \$\begingroup\$ @PeterCordes Ah, I need to brush up on my floating point I guess. Thanks for the info! \$\endgroup\$
    – Chris
    May 17 at 4:46
2
\$\begingroup\$

Vyxal , 10 bytes

k⁋E*÷꘍k⁋E/

Try it Online! or Verify all test cases!

For the 0.002000000000000001 ^ 0.002 test case, it unfortunately fails because it seems to automatically round it to 0.002. It does work with three zeros removed, though. This seems to be a problem with sympy.nsimplify:

>>> sympy.nsimplify(0.002000000000000001, rational=True)
1/500
>>> sympy.nsimplify(0.002000000000001, rational=True)
2000000000001/1000000000000000

(from Python REPL)

How?

k⁋E*÷꘍k⁋E/
k⁋         # Push 1024
  E        # Push 2**1024
   *       # Multiply the (implicit) input pair by that
    ÷      # Push both elements of the multiplied pair to the stack
     ꘍     # Bitwise XOR them
      k⁋E/ # Divide by 2**1024
\$\endgroup\$
4
  • 1
    \$\begingroup\$ @PeterCordes By the way, it is not broken for the 1e300 test case. It is only broken for the 0.002000000000000001 case due to an issue with Sympy. Also, 1.2e-20, 1.5e-20 does not wrongly give 0.0, it gives 2.678658729691487e-20. \$\endgroup\$
    – Steffan
    May 12 at 17:50
  • \$\begingroup\$ Oh, sorry, I just commented after seeing you say it was a port of those other two answers, reposted my comment from there under the assumption it would have the same bug, to maybe get your attention while you were still here. I guess Vyxal uses or lets you use rational numbers instead of straight IEEE binary64 floating point? That could let it work for huge numbers, but tiny inputs below 2^-64 or 2^-100 would still not have all their significant bits in the integer part unless you use a multiplier like 2^1022 \$\endgroup\$ May 12 at 17:55
  • 1
    \$\begingroup\$ @PeterCordes Vyxal uses Sympy under the hood, and I believe it's because Sympy works on rationals. But I don't know. I will change it to 2^1022, it will only add 3 bytes. \$\endgroup\$
    – Steffan
    May 12 at 17:56
  • \$\begingroup\$ (And BTW, Kevin's answer works for 1.2e-20 because he used 2^100 instead of 2^64. But 1.2e-40 has the same problem as the original Python answer, and yes I tested those.) Anyway, cool, that'd work with Python's arbitrary precision integers. You should probably add some text to your answer to explain why this works, despite the other answers only working in about half the exponent range of IEEE double inputs, with the multiplier determining where that slice is located. \$\endgroup\$ May 12 at 17:56
1
\$\begingroup\$

Julia 1.0, 51 bytes

f(a,b,e=8^341.)=e>0&&(a÷e+b÷e)%2*e+f(a%e,b%e,e/2)

Try it online!

port of m90's answer

I tried so many things but always landed on 51 bytes

\$\endgroup\$
0
\$\begingroup\$

C (gcc), 87 bytes

typedef double d;d c=1LL<<32;d x(d a,d b){return((long long)(a*c)^(long long)(b*c))/c;}

In the spirit of the Python answer above, converts to a fixed point integer and does the XOR, before converting back. It only has 32 bits of precision to either side of the decimal point, assuming long long is 64 bits wide, which is exactly the worst precision allowed by the challenge (1e-6). Because of this, the 1e300 answers overflow.

If your platform has 64-bit longs 11 bytes can be saved, for a total of 76 bytes:

typedef double d;d c=1L<<32;d x(d a,d b){return((long)(a*c)^(long)(b*c))/c;}
\$\endgroup\$
4
  • \$\begingroup\$ The x86-64 System V ABI uses 64-bit long (as on Linux / MacOS / any non-Windows, including tio.run). So do most C implementations for 64-bit ISAs outside of Windows. To use that as your main answer, you really only need one such implementation to exist (meta rules say answers must work on at least one implementation), but in this case it's also widespread. \$\endgroup\$ May 12 at 17:10
  • 1
    \$\begingroup\$ It only has 32 bits of precision to either side of the decimal point - no, floating point can have the decimal point (err binary radix point) anywhere relative to the mantissa. 1.23e-20 has all 53 mantissa bits representing the fractional part, with many zeros above it. e.g. have a look at how 32-bit float represents 1.23E-20 on h-schmidt.net/FloatConverter/IEEE754.html, as a mantissa of 1.815159559249878 multiplied by 2^{-67} encoded by the exponent field separately. Your 32:32 sounds like fixed-point. \$\endgroup\$ May 12 at 17:17
  • \$\begingroup\$ And BTW, the Python answer that inspired your answer is also wrong. Even arbitrary-precision Python math can't save it from the overflow in double-precision multiply, and thus even a huge multiplier like 2**1022 couldn't make it correct. (Unfortunately I wasn't thinking when I upvoted it; now I can't downvote until it's edited.) \$\endgroup\$ May 12 at 17:34
  • \$\begingroup\$ 69 bytes \$\endgroup\$
    – ceilingcat
    May 14 at 20:13
0
\$\begingroup\$

Stax, 25 bytes

∩√=êⁿ;r⌂$══▓ìêCO¥ÇnµtƒÉd+

Run and debug it

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.