The Nineteenth Byte

@Ausername Stalin sort

GPT-2

lyxal

12:21 PM

GPT-3

with dark mode too

I mean, at least GPT-2 generates english

Neil

@Ausername that's nothing. the empty set denotes, even though it doesn't denote anything

@Neil Ok...

2

does anyone know R well enough to tell if codegolf.stackexchange.com/a/230419/7310 is really linear time?

Neil

e.g. all members of the empty set are odd, even, square, cube, prime and composite

12:23 PM

Oh true...

More GPT-2

'night

Luis Mendo

@flawr Feel like convolving stuff?

CMQ: Name an O(n) sort algorithm.

@Adám count sort, radix sort, just leaving the input as it is :)

depends on what the input looks like

@Adám count sort is linear time if the input is integers in a small range

@Adám radix sort is linear time if the input is integers in the range 0..n^c for a constant c if the input is of length n integers.

curiously you can convert from C doubles to 64 bit integers and back without any loss

12:43 PM

@felipa What is count sort?

Counting sort

In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the difference between the maximum and minimum key values, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of...

@felipa Of course, they are all just 64 bits. Doesn't matter what the bits represent.

en.wikipedia.org/wiki/…. is also linear time under the right circumstances

specifically if the input is uniformly distributed

@Adám yes but the key point is that the order is preserved

@felipa That sounds suspicious. Some 64-bit patterns do not represent orderable floats.

@Adám you need them to follow IEEE754

which I think essentially always happens

12:49 PM

@felipa I still don't get it. E.g. is qNaN<sNaN?

@Adám is that a floating point nan?

Yes.

if it's nan that I guess there is no defined order so you can do what you like with it

5 mins ago, by felipa

@Adám yes but the key point is that the order is preserved

how is nan represented in bits in IEEE754?

@Adám that's right. The order of things that had order in the first place

like 7 and 13

12:52 PM

@felipa s111 1111 1xxx xxxx xxxx xxxx xxxx xxxx

@felipa But surely, any IEEE754 NaN must correspond to a 64 bit int.

@Adám sure. Maybe the range is 63 bits in that case?

We need an expert :)

@felipa Well, there are 16777214 IEEE754 NaNs, all the ints they correspond to are problematic.

so it could still be 63 bits?

If feel writing some code and trying it out could help here

I guess. Since all floats that begin with s0 are normal floats.

that sounds good

12:58 PM

Not very curiously, you can convert from C doubles to 63 bit integers and back without any loss.

and preserve the order!!

If that even holds. I'm not so sure this is even true.

that's the clever bit

It it was true.

However, some floats have multiple valid bit representations. Clearly, these values should be considered equal (even if only one is the normal form), and thus they don't have the same ordering as the integers they correspond to.

1:27 PM

can you give examples?