PSA: If some of you missed it code-golf.io also allows Haskell submissions. I feel like the Haskell golfers should be more present and I could certainly do with some more competition ;P

@BMO I tried the primes challenge but didn't get anywhere close even with this integer-based algorithm you can find

For primes you need to use probabilistic methods

sorry, I confused the primes with the digits of pi challenge:)

Check out some of primo's answers on this site for pi inspiration

Why does main = mapM print [1,2,3] work?

This has the type IO [()], but I thought we must have main :: IO ()?

main just has to have the type IO a

oh

D:

@H.PWiz only 5 more bytes to go :)

@H.PWiz I've been wondering for days how you managed that score :S

@flawr Which integer-based algorithm?

I think, given enough time/resources, pretty much any algo could be adjusted to integer math, st. it would be possible to compute the first 1000 digits.. But I'm not good enough with maths :(

I've been trying to get this to work, but it does not converge at all..

@H.PWiz Can you solve Emirp?

@BMO this one: cs.ox.ac.uk/jeremy.gibbons/publications/spigot.pdf

@flawr: Ah, but that one is for computing the digits individually, right?

My solution is along the lines of main=putStr$"3."+show(....)

@BMO I mean using that idea, not in general ;)

@BMO oh so you just interpreted the digits after the decimal point as one huge number? (and wrote something that computes this number?)

@flawr Yes, along the lines of 10^1000*1`div`3

@BMO how long did that take you? D:

@flawr Initially, I tried that algo as well but it was way too long

@flawr You mean for computing?

@BMO how long did it take you until you got a representation that was short enough using this method? :)

@flawr I can't remember, but quite a while..

I thought so :)

Though, I'm certain I spent a lot more time on trying to implement this and I still haven't managed to :(

Probably because I suck at numerics

@BMO do you want to use it for the pi digits challenge?

Well my idea was "to stretch" it somehow to a 1000-digit integer and use that, yes

@BMO you can easily find a limit of how many terms you ahve to use

you can use Rational numbers to compute this approximation. Then you could maybe multiply by 10^1000 and use properFraction or something like that.

oops no, this looks like it needs in the order of 10^1000 terms to converge to the accuracy we need :/

(the error term is O(1/n), which is pretty bad )

@H.PWizard how the heck can you shave off 4 more bytes here? code-golf.io/scores/fibonacci/haskell

@flawr I think that would be prohibitively expensive to use, but in any case my current implementation didn't get near an error of O(1/n) ..

@flawr Yeah, I was wondering the same..

Also, how would you even get close to Conway's constant? Seems like the straight forward way of implementing the actual series will never converge.. Probably we'll need to golf that polynomial and start approximating the solution to it -.-

@BMO yes, that seemst to be the only way

@BMO I have an idea:)

@BMO It looks like this polynomial has exactly one zero between 1 and 2, so we could use the bisection algorithm to approximate the root. This needs log2(10) = 3,... iterations per digit, so we need just around 3k iterations.

You'll still need to encode that polynomial which is quite expensive, right?

Now this will result in an ugly denominator. If we want to compute digit by digit, instead of a bisection we can use a 10-section

yep that is a harder part:/

@flawr That's where I stop thinking about that particular problem, haha

but even by just hardcoding the coefficients I'm sure we can get a lot below the current entries

hold my beer cup of hot chocolate

@flawr I'm with hot glühwein rn, but yeah that's quite likely

Also, how would you not get 1015 bytes (@retrohun)?

using too many spaces?:)

@BMO my fully commented version beats the current ones solutions:)

(well I haven't met the exact output yet

time to golf

NOOOOO

it takes too long :...(

golfed version

Turns out evaluating a polynomial of degree 71 gets expensive soon

@flawr Fibonacci's fun, not a technique you see much on this site

@BMO Yeah, some solutions use the polynomial, others compress it. I don't have any clever Haskell compression, especially since it's quite fussy about what unicode characters it lets you use

@flawr Newton's method may also be good

newton's converges quadratically for zeros with multiplicity 1, right?

No idea

@BMO putStrLn vs putStr

@BMO I'm nervous because I suspect hardcoding will be shorter with the right method

@H.PWiz Are you actually abusing this in any submission? Can't think of any solution where that could be useful..

@H.PWiz Ouch :P

@BMO I compress it in bash :)

@H.PWiz Thought so :D

@flawr That's crazy ^^

@H.PWiz I use f=0:scanl(+)1f for fibonacci - you're saying there is something shorter?

Ungolfed and commented, still beats them xD

@flawr My solution is shorter than your solution...

@H.PWiz yeah, maybe the printing is the par tthat I'm doing worng :)

@BMO You can easily fit 6 digits (no leading zeros (easily)) in a character

@H.PWiz Wait a sec, so you're using string-compression in some puzzles!?

(don't spoil which ones though)

@BMO Not in Haskell, I haven't understood what characters are allowed in a Haskell program

@H.PWiz As far as I know, Haskell is really liberal.. There's one submission on cg.SE where we were able to leverage some really weird unicode-whitespace chars and it accepted them as actual whitespaces

Oh I did investigate that once...

There is a limit to the magnitude of a codepoint allowed in source. I can't remember what it was, but it includes characters inside strings

It's not based on magnitude, it's based on Unicode character classes.

Oh,

You can check with Data.Char.generalCategory.

@H.PWiz my problem then is: how do you convert the fraction (probably with a huge denominator) back to decimals?

That's a real pain. (the character stuff)

@flawr I don't know. I'd be inclined to find a way that lets you converge to 10*1000*<conway's constant>. And then use integer ops

@H.PWiz ah wait, we can use newton and then multiply by 10^1000 and then use properFraction as I suggested above

Cool! does floor work on rationals?

or are you using properFraction to force the type inference?

Oh right, floor should work too!

oh and round no need for properFraction

About 112802 characters are permitted out of the 1114111 total.

I count 112320

Oh wait there's something weird about OtherPunctuation

I got it in both allowed and forbidden.

Oh I see, the only OtherPunctuation that are forbidden are " and \

(Well forbidden as in don't stand for themselves)

@H.PWiz The string I've got literally in the program definitely contains 112802 unique characters.

@ØrjanJohansen My count was based on your list.

Not actually checking, 112802 is right

Oh I see. Hm...

Oh also I'm on GHC 8.0.1 still (every time I consider upgrading I hear about some fiendish bug), so it's possible the Unicode database has got upgrades since.

(Which would probably add a heap of emoji...)

With your amendment about OtherPunctuation, I count the same (ghc 8.6.3)

@ØrjanJohansen Are you using GHC as part of an important toolchain?

Oh BTW "forbidden character classes in strings" should be in string literals, in case someone misunderstood - the Char type itself allows everything between 0 and 1114111.

@BMO Certainly not, I'm purely a hobbyist and these days I rarely do more than the occasional golfing.

Oh, what's keeping you from updating then?

@BMO I use that, but under the euler transform. Then with some golfs

Well right now the last release has a horrible TH crash on Windows...

And I think they still haven't fixed the bug where GHCi can crash if you run an IO action which isn't IO ()

@H.PWiz unfortunately the newton method is also too slow see here

Also I'm extremely lazy but that goes without saying.

@ØrjanJohansen which is why you're using Haskell in the first place

Precisely!

Yep, I reckon there is some maths to change it to converge to 10*1000*λ directly, bypassing slow rationals

@H.PWiz you could just scale the polynomial function by 10**1000 in x-direction?

but I don't think that this would help?

I think that might multiply some coefficients by 10**71000

or thereabouts

oh, you could always round the intermediate steps to integers then!

good idea

How do you "multiply" the zeros of a polynomial by a constant? I was thinking about modifying the recurrence for newtons method

@H.PWiz replace p(x) with p(x/a) to "scale" it in x-direction by a factor of a

Oh no... division. But I want integers :(

Replace it by p(x/a)*a^71

ninja'd

in this case a=10^1000

Good idea

but that means the coefficient get just insanely large. I do not think this is much faster than just using fractions, or is it?

The fractions might accumulate insane denominators just by accident, though

@H.PWiz Ok, currently I'm doing sth. different. I'll investigate where I can go from there

At least with integers you can round.

@ØrjanJohansen That does sound rather annoying..

@ØrjanJohansen let me try :)

but maybe another day

merry christmas by the way, for those who are in the right time zone :)

merry christmas

I'm gonna have to get some sleep. Thanks for all the suggestions!

@flawr All the same to you (we're certainly in the same time zone ;P)

And merry christmas to everyone else :)

One might think so :)

(Does that mean you're in the same building...)

btw: I tried decomposing the polynomial in the hope that it will be quicker to evaluate, but it didn't yield a decomposition=/

(it does not, at least I hope they're not in my basement)

@ØrjanJohansen I'd be very surprized :D

@BMO hehe, nice wine you have down here

I think if Conway's polynomial had any factors he would have published that instead ::P

@flawr Ungolfed. unfortunately off by one: tio.run/##ZVDNT8MgFL/zV7DEA0wgPNqCmPTmxZOJFw/…

@ØrjanJohansen I mean decomposing into a composition like p(x) = g(h(x))

@H.PWiz wow, that looks great!

but I really should go now, I'll have a look at it tomorrow!

Newton converges very quickly

An off by one is easy to fix by cheating, I should think.

(Remembering the e discussion from the other day)

I meant 50 instead of 49 at the end. Can be fixed by just -1 (as I did)

Also, I've given up on anagol e for a while.