The Nineteenth Byte

In computer science and numerical analysis, unit in the last place or unit of least precision (ULP) is the spacing between floating-point numbers, i.e., the value the least significant digit represents if it is 1. It is used as a measure of accuracy in numeric calculations. == Definition == In radix b, if x has exponent E, then ULP(x) = machine epsilon · bE, but alternative definitions exist in the numerics and computing literature for ULP, exponent and machine epsilon, and they may give different equalities. Another definition, suggested by John Harrison, is slightly different: ULP(x) is...

Alex A.

I feel like there's all this fancy computer science terminology I don't understand, like "shit difference," "ulp," "giggleth"...

8

Thomas Kwa

12:34 AM

I think APL considers numbers equal if the ratio is less than (1+2^-32)

Alex A.

@ThomasKwa That is an interesting factoid. Where did you find that information?

Thomas Kwa

I'm not sure about it

I just looked up some site about an APL implementation, and then I tested it

doesn't seem to be exactly right now, though

Alex A.

Which implementation was it? I know Dyalog and ngn give different results for floating point equality.

Thomas Kwa

SHARP APL

Yeah, it's definitely not correct with Dyalog

Alex A.

I've never heard of SHARP APL!

Thomas Kwa

12:40 AM

oh, here's what Dyalog uses:

dyalog.com/uploads/documents/Papers/tolerant_comparison/…

I feel like I've read that article before, but I don't remember when.

it's (|x-y)≤⎕ct×(|x)⌈(|y) for some ⎕ct ≤ 2^-32

Alex A.

My default Dyalog desktop comparison tolerance is 1E¯14

Thanks for the link, @Thomas. That's helpful.

El'endia Starman

Okay, so, there's a really old question on Huffman encoding, which asks for a Huffman tree. What I had in mind was that programs would compute the Huffman coding and then output each character along with its binary representation, sorted from shortest/most frequent to longest/least frequent. Are these different enough that they wouldn't be duplicates?

Thomas Kwa

1:01 AM

It would not be a duplicate, because you can't trivially modify answers to that question to answer your new question.

El'endia Starman

Excellent.

I shall sandbox it now.

Anonymous

2:13 AM

@AlexA. I like (in C) FLT_EPSILON or DBL_EPSILON, which are the difference between 1 and the smallest representable value greater than one, in IEEE 754 single- or double-precision floating point representation, respectively. Alternatively, if you're dealing with values far from 1 (such that precision is noticeably affected), doing the same specification, but with the goal value instead of 1, works well.

SuperJedi224

Hi

Anonymous

Hi Jedi

quartata

Now that I have MLG editing powers, is it OK to edit answers to include a link to run the code in an online interpreter?

I don't want to step on any toes or anything but I see some answers every once and a while where it would be nice

Thomas Kwa

"MLG"?

undergroundmonorail

major league gaming

Thomas Kwa

2:17 AM

I don't know; you could ask on meta.

El'endia Starman

Okay, just posted in the sandbox. Let's see how long the bot takes...

quartata

Ooh new challenge

Sp3000

Leave a comment, I'd say. Just in case they had a reason

SuperJedi224

So... dropsort. Do you think it merits a question here?

quartata

@Sp3000 Alright.

SuperJedi224

2:19 AM

dangermouse.net/esoteric/dropsort.html

quartata

Wow I was dividing some numbers by 10^x in Mathematica to get rid of the 0s on them

El'endia Starman

> Dropsort is what is known in the computer science field as a lossy algorithm. It produces a fast result that is correct, but at the cost of potentially losing some of the input data.

quartata

And I was just looking at this one and guessed 10^54 and it got all the 0s off without getting rid of any other digits

I guess that was a hole-in-zero

El'endia Starman

Haha, nice!

quartata

0

A: The Mystery String Printer (Cops)

Mathematica Range: <= 64 String: 368921261379020282513891270954327186982974673706213278032469400595412966847044520376177106248857169605480346489563721888158441477887340357265444593721230093185417136793217614909721283425696418258308730582895596139457963926138833267594357117764501504

Sadly it was not enough to get it below 32 bytes...

I actually have a feeling this might get cracked fast

New Sandboxed Posts

2:24 AM

0

A: Sandbox for Proposed Challenges

Code the Huffman! code-golf Or else he will huff and puff and blow your house down! That was completely irrelevant. This challenge is actually about Huffman coding. The gist of it is the frequency of characters in a given text is utilized to make its representation shorter. In other words, let...

Anonymous

@quartata I'd say no. Editing other people's posts is typically used to fix formatting/spelling and such. Adding a link to an online interpreter doesn't constitute a necessary edit to me - you should comment with a link instead.

quartata

@NewSandboxedPosts That was 7 minutes not bad

@Mego OK

El'endia Starman

^^

Anonymous

carrot.jpg

El'endia Starman

Video of people running backwards, reversed.

~~That's taking a while to load.~~

quartata

2:26 AM

> Or else he will huff and puff and blow your house down!

SuperJedi224

So do you think I should post a dropsorting task?

Anonymous

@El'endiaStarman imgur has been taking forever today

Anonymous

@SuperJedi224 post it in sandbox and see how it goes

El'endia Starman

@Mego The actual issue is that it's a .webm or .gifv, but those don't one-box.

....would they if I used !? Answer: nope.

Anonymous

i.imgur.com/7UbK4OW.webm

Anonymous

2:29 AM

Hmm

TheDoctor

hi

wow, 9 stars on my stars

SuperJedi224

@Mego Okay, I'll do that later.

Anyway, I've got to go for now.

Bye.

Anonymous

Bye

El'endia Starman

2:54 AM

I'm seeing LaTeX equations flash in and out of existence... o_O

Anonymous

@El'endiaStarman story of my life

GamrCorps

I'm trying to develop a chrome extension

to do just that

Anonymous

LaTeX?

El'endia Starman

There already is one.

Anonymous

You mean like TeXEverywhere?

El'endia Starman

2:55 AM

I'm using one.

GamrCorps

Well that would explain why you see it too

I'm trying to use this as a way to learn some javascript

Anonymous

Err, TeX The World

Anonymous

chrome.google.com/webstore/detail/tex-the-world-for-chromiu/…

Anonymous

Is gud

El'endia Starman

SE Chat MathJax Chrome extension

GamrCorps

2:56 AM

$$\int_0^R r^2dm$$

Yes! I got it to work!

Anonymous

Neato

El'endia Starman

@GamrCorps *is tempted to replace that dm with dr...*

GamrCorps

lol

Anonymous

flags as nonsensual

El'endia Starman

pffft!

GamrCorps

2:58 AM

Now if only we could have this in challenges, just would have to change the operators to something non-code.

New Sandboxed Posts

0

A: Sandbox for Proposed Challenges

Lossy Sorting (Implement Dropsort) code-golfsorting Dropsort, designed by David Morgan-Mar, is an example of a linear-time "sorting algorithm" that produces a list that is, in fact, sorted, but contains only some of the original elements. Any element that is not at least as large as the maximum...

Dennis

El'endia Starman

Congrats @quartata!

4

GamrCorps

wow

neato!

Its even more impressive that it is 1000 on the dot.

Anonymous

downvotes

TheDoctor

3:02 AM

:P

★

Doorknob

/me considers suspending TheDoctor if he types that symbol or the word "star" again, for the millionth time

6

GamrCorps

^

Dennis

@AlexA. Option B was φ as in bee, right? The fahyl was just a joke.

TheDoctor

/me wonders whether @Doorknob really uses IRC or is just pretending

Anonymous

@TheDoctor IRC? Is that a Nethack clone?

Doorknob

3:06 AM

I do use IRC :P

GamrCorps

@AlexA. its pronounced "fi" (like "fly" without the 'l')

Anonymous

φ φ fo fum I smell the blood of an Englishman

TheDoctor

@Mego >.> irc is like 40000000000 years old

GamrCorps

correction: fee φ fo fum I smell the blood of an Englishman

quartata

Oh hey I missed my 1k rep congratz

GamrCorps

3:07 AM

congrats again!

quartata

Thanks!

TheDoctor

Anonymous

@TheDoctor I was making a joke because @Doorknob and his Nethack love

GamrCorps

@TheDoctor some people.....

Anonymous

@TheDoctor I bet Mathematica has a builtin for that

3

GamrCorps

3:09 AM

^

Anonymous

carrot.jpg

Anonymous

I'm trying to be a faster carrot than @Dennis but it's hard

undergroundmonorail

recently i found out that mathematica has a lot of builtins that, the first time you use them, download the code from wolfram servers

Anonymous

:o Dennis why did you change your avatar back

undergroundmonorail

so you don't have a million things you'll never use in your mathematica

that's kinda cool

Anonymous

3:10 AM

Yay lazy evaluation

Dennis

@Mego Nobody seemed to be getting the reference anyway. :/

Anonymous

@Dennis You explained it and I still didn't get it

quartata

I got the reference :/

Anonymous

You should photoshop a pumpkin on Dennis's head or something

GamrCorps

better yet: make him orange

TheDoctor

3:11 AM

everyone is pumpkin

Dennis

@Mego I rest my case.

Anonymous

@Dennis tbh that's probably more on me than you

TheDoctor

my dog found out that he really like to eat pumpkins. He ate several of our jack-o-lanterns :/

Anonymous

My brain is like

Dennis

So many stars on the star board...

Anonymous

3:13 AM

"Write a proof about optimal ingredient picking for n different ingredients to make pies with k distinct ingredients? No problem. Understand jokes/pop culture references? hurr durr"

quartata

He is just one person. You need several more people for statistical significance

TheDoctor

@Dennis not anymore :/

Dennis

I still see them.

quartata

carrot.jpg

2

TheDoctor

your screen is bigger than mine

Anonymous

3:14 AM

Hey @TheDoctor what's your favorite pathfinding algorithm that uses heuristics to improve performance?

TheDoctor

<s>i dont really use search algos</s> i'm a dog, i sniff

why do you ask?

Alex A.

The Doctor doesn't need to search for anything; he knows the location of all things at all times.

Anonymous

Because the answer should be A-star

3

Dennis

OK, now the stars are gone.

3

Doorknob

@Mego Dijkstra's. Now what? :P

Anonymous

3:16 AM

@Doorknob Dijkstra's algorithm doesn't use heuristics, which is why I had to explicitly mention heuristics

Doorknob

it doesn't?

Anonymous

Nope

Dennis

There are so many words in here I don't understand:

4

2 mins ago, by Mego

Hey @TheDoctor what's your favorite pathfinding algorithm that uses heuristics to improve performance?

quartata

A* is lame. You should try a red giant.

TheDoctor

@Mego my nose

feersum

3:18 AM

Scent gradient descent.

Anonymous

@Dennis You have a weighted acyclic digraph, and you want to find the shortest path between two nodes. Dijkstra's algorithm does that. A* does that too, but uses heuristics to hopefully do better. A* is identical to Dijkstra's in the worst case (when the heuristics are wrong/non-existent), but on average is much faster.

quartata

*crickets*

GamrCorps

Hey @Dennis, in CJam, is there any shorter way to turn a string array into an integer array than this: ["1""2""3""4"]{i}%?

Doorknob

Every programmer's made this commit message at some point in time... or at least something similar

quartata

No one got my joke?

Dennis

3:20 AM

@GamrCorps :i

TheDoctor

4

GamrCorps

@Dennis thanks!

Dennis

@Mego If I didn't understand pathfinding algorithm and heuristics to improve performance, I'm not going to understand weighted acyclic digraph... :P

GamrCorps

^

Alex A.

^

Dennis

3:23 AM

I seem to have misplaced my carrot.

6

Alex A.

Topologists aren't concerned with improving pathfinding performance heuristically. All of their graphs are weightless, cyclic, and trigraphic.

quartata

ELD5 (Explain Like Dennis is 5)

3

undergroundmonorail

> All of their graphs are weightless, cyclic, and trigraphic.

Dennis

2

undergroundmonorail

just like YO MAMA

TheDoctor

3:24 AM

i'm going to run out of stars before tomorrow :/

Alex A.

20 mins ago, by Doorknob

/me considers suspending TheDoctor if he types that symbol or the word "star" again, for the millionth time

TheDoctor

sorry

Alex A.

Just a reminder. :P

Anonymous

@TheDoctor I'm going to run out of stars before I go to bed :P

TheDoctor

^

quartata

3:25 AM

@undergroundmonorail rekt

Alex A.

I will never, ever run out of stars. ಠ_ಠ

GamrCorps

Darn, I ran out of stars for today...

undergroundmonorail

*mlg airhorns*

quartata

ohhhhhhh

Alex A.

Thomas the Dank Engine

Dennis

3:25 AM

@AlexA. You can always pin.

undergroundmonorail

WHERE YOU AT? WHERE YOU AT? WOMBOOOO COMBOOOOOO

quartata

dew n doritos

mum get the camera

TheDoctor

https://www.eff.org/issues/tpp >> http://cms.fightforthefuture.org/tpp/
"The Trans Pacific Partnership includes provisions that would lead to extreme Internet censorship and undermine democracy and national sovereignty. I demand that my government oppose this agreement and refuse to sign."

^ that should be pinned

undergroundmonorail

i've always enjoyed the wombo combo because of the yelling, basically, but now that i play melee it feels almost sacred

like i get it now

Anonymous

@Dennis A graph is a collection of nodes and vertices connecting those nodes (usually in a 2D plane). A digraph (or directed graph) is a graph where the vertices only go one way - A->B does not imply B->A (where in an undirected graph, all vertices are two way: A<->B). A weighted graph is a graph where the vertices have weights associated with them, usually representing the cost to traverse the vertex.

Anonymous

3:28 AM

@TheDoctor Will it ban code golf?

TheDoctor

maybe

Vɪʜᴀɴ

I finally made a good interpreter design for once. link

quartata

Wombo combo will always have a special place in my heart. Melee is the only SSB. All others are imposters. drops mic

TheDoctor

boom

quartata

@Vɪʜᴀɴ oh wus dis

Alex A.

3:29 AM

büm

quartata

Oh hey its TeaScript.

Dennis

@Mego So far I'm with you. Still not sure how it's related to A★ though...

Anonymous

Is it supposed to work?

quartata

This is going to sound dumb but are there any shorter ways of printing aside from the implicit final result printing @Vɪʜᴀɴ

TheDoctor

3:33 AM

print

Vɪʜᴀɴ

@quartata uh nope. not yet probably should of thought of that sooner

Anonymous

@Dennis Pathfinding algos try to find a path between two nodes, preferably with minimal total weight. Dijkstra's algorithm is a fairly simple one. The A* algorithm is an improvement upon Dijkstra's, allowing heuristics to be given that improve the speed of the algo.

quartata

ah OK.

Alex A.

★ 2

Dennis

I am rocking the star board right now.

2

TheDoctor

3:35 AM

me 3

ish

Dec 10 '14 at 15:26, by Martin Büttner

@TheDoctor he refuses to change his name to Snowbolt though, which makes all of us very sad. :(

Geobits

Dennis

This is pretty big for me, considering that I reached 15k rep before the Talkative badge. :P

TheDoctor

github.com/mniip/Doger

Anonymous

@Dennis do you understand the pathfinding stuff now?

Dennis

I think I get what pathfinding is, but I guess I'd have to read a couple of things before understanding the part about heuristics.

Alex A.

3:43 AM

@Dennis You sat in brooding silence amidst a bombardment of CJam upvotes.

El'endia Starman

@Dennis Heuristics is basically just picking a choice out of at least two that's probably better.

In the case of A*, the heuristic is distance to the goal. So if a choice moves you towards the goal, it's probably a better choice than one that moves you away.

Anonymous

^ basically that

Anonymous

Dijkstra's algo works similarly to a depth-first search

Anonymous

Where it explores a path until the cost is greater than a potential other path

feersum

Isn't Dijkstra more like a BFS?

Anonymous

3:48 AM

Heuristics allow you to say that certain vertices are probably more optimal than others, so it tries those first

feersum

It looks at the nodes which are closest to the start.

Anonymous

@feersum tbh it's kind of somewhere between both

feersum

With unit weights, would it not be exactly a BFS?

Anonymous

Yes

Anonymous

But non-unit weights muddy the resemblance

Anonymous

3:50 AM

Actually yeah it's more BFS than DFS

Anonymous

Fancy Dijkstra's algo gif:

Anonymous

And A*, with heuristics supplied such that more distance from start is better:

Anonymous

Dennis

You should have started with the GIFs. :P

2

Anonymous

3:55 AM

Yeah I get that a lot

Anonymous

Both algos try to find a path that minimizes f(n) for node n, which is the cost to travel to n

Anonymous

(from the start)

Anonymous

Dijkstra's calculates f(n)=g(n), where g(n) is the best path it has found so far

GamrCorps

redblobgames.com/pathfinding/a-star/introduction.html

neat little interactive a* thing

Anonymous

A* uses f(n)=g(n)+h(n), where g(n) is the same as in Djikstra's, and h(n) is the heuristic estimate of the actual cost

Anonymous

3:58 AM

The GIF above uses h(n) = dis(n), where dis(n) is the Euclidean distance from the start

Anonymous

So long as h(n) is less than or equal to the actual cost, A* will find the shortest path, with at most as many steps as Dijkstra's

Anonymous

With h(n)=0, it's identical to Dijkstra's

Anonymous

My OOP question can also be solved with graph theory, by making a connectivity matrix

Anonymous

Anyway, after that fascinating lesson on pathfinding, I'm going to bed

Dennis

Good night!

And thank you for ELI5.

Alex A.

4:30 AM

Recommended YouTube video for me: "Cat Thug Life - Ultimate Cats Thug Life Compilation!"

ಠ_ಠ

10 hours ago, by Alex A.

Like one time on Facebook I joking said #thuglife and now I always get Tupac ads.

Apparently it carries over onto other sites.

Dennis

If I needed a reason not to use Facebook, this would be it.

6

New Main Posts

1

Q: Find the angle between two points

Given two points A and B, find the angle from line AO to line BO about point O where O is the origin ((0,0)). Additionally, the angle may be positive or negative depending on the positions of the points (see examples). Input will be points A and B, and may be given in any convenient form. Output ...

code-golf math trigonometry

El'endia Starman

@NewMainPosts ....I should probably implement trig functions in Minkolang.

sin and cos at the very least. Their inverses too.

....um. 3 CJam answers?!?

Transcript for