# [a b] [e f]
# [c d] [g h]
def matrix_mul(A,B):
    [a,b,c,d] = A
    [e,f,g,h] = B
    return [a*e+b*g, a*f+b*h, c*e+d*g, c*f+d*h]

# [a b] [a b]
# [c d] [c d]
def matrix_square(A):
    [a,b,c,d] = A
    temp = b*c
    return [a*a+temp, a*b+b*d, a*c+c*d, temp+d*d]

def fast_matrix_pow(A,n):
    if n==0: return [1,0,0,1]
    if n==1: return A
    temp = fast_matrix_pow(A,n>>1)
    temp = matrix_square(temp)
    if n%2 == 1:
        return matrix_mul(temp,A)
    else:
        return temp

def fast_fib(n):

<< 0
<< 144

o_O needs more numpy

@Sp3000 I don't like built-ins

Hello

@zʏᴀʙiɴ101 hi

why did you change to small caps

traitor

Am chatting on the PC now, because mom stole my phone this night.

# All the matrices used
# in Fib generation
# has the form:
# [a b]
# [b c]
def fast_matrix_pow(n):
    if n==0: return [1,0,1]
    if n==1: return [1,1,0]
    [a,b,c] = fast_matrix_pow(n>>1)
    tmp = b*b
    a,b,c = a*a+tmp, (a+c)*b, tmp+c*c
    if n%2 == 1:
        return [a+b,a,c]
    else:
        return [a,b,c]

def fast_fib(n):
    return fast_matrix_pow(n)[1]

print(fast_fib(0))
print(fast_fib(12))

@Fatalize ಠ_ಠ

<< 0
<< 144

@zʏᴀʙiɴ101 spins anti-lightsaber baton

The first-order does not respect small caps

# All the matrices used
# in Fib generation
# has the form:
# [a b]
# [b c]

# [a b] \/ [a b] -- [a*a+b*b a*b+b*c]
# [b c] /\ [b c] -- [a*b+b*c b*b+c*c]

# F(2n) = (F(n-1) + F(n+1)) * F(n)

# [a b] \/ [1 1] -- [a+b a]
# [b c] /\ [1 0] -- [b+c b]

@Mego Could I implement it in your language?

This is O(log(n)) time algorithm

Computes F(1000000) in a fraction of a second

def fast_matrix_pow(n):
    if n==0: return [1,0,1]
    if n==1: return [1,1,0]
    [a,b,c] = fast_matrix_pow(n>>1)
    tmp = b*b
    a,b,c = a*a+tmp, (a+c)*b, tmp+c*c
    if n%2 == 1:
        return [a+b,a,c]
    else:
        return [a,b,c]

def fast_fib(n):
    return fast_matrix_pow(n)[1]

print(fast_fib(0))
print(fast_fib(12))

It is based on the following fast_power algorithm:

def fast_pow(int b, int n):
    if n<0: return 0
    if n==0: return 1
    if n==1: return b
    temp = fast_pow(b,n>>1)
    return temp*temp*[1,b][n%2]

@Mego For 3. can't you just disable recursion errors?

ideone.com/jPFGgM

@LeakyNun Not log base 2?

@Mego No

It computes F(100000) in 0.11 seconds

@MᴀʀsUʟᴛᴏʀ edited. satisfied?

You don't need anywhere near infinite memory

uh

No, Big O notation is only for complexity

of time as well as memory

@LeakyNun But you're using it for the number of stacks

Alright, I don't care.

ideone.com/jPFGgM

@Mego If you do need infinite memory for Fibonacci, then it's at around 2^recursion_depth

@LeakyNun Why not just use Binet's formula?

Could anyone knowledgeable tell me how hashtable works?

(It's not related)

@MᴀʀsUʟᴛᴏʀ Precision.

@LeakyNun It's probably faster for numbers where it's precise

@MᴀʀsUʟᴛᴏʀ Precision before speed.

@LeakyNun Just use binet's formula up to powers where it doesn't work

okay, I'll implement that.

@LeakyNun In most languages, there are hash functions for various types of objects, including strings. Basically, a hashtable is like a sparse array of hash -> value (IDK how sparse array lookup works though)

@MᴀʀsUʟᴛᴏʀ I know how hash works, but how does the table work?

let's say you generated a hash for a string

and the hash is 9b185dbc

and then what do you do?

@LeakyNun Wikipedia says mod to array size

then store there. if there's a collision, do some further logic

@Mego What linked list?

why a linked list?

oh, in case of collision

@LeakyNun BTW, for the binet you should probably store 1+qrt(5), 1-sqrt(5) and sqrt(5) as constants

def binet(n):
    phi = 1.618033988749895
    sqrt5 = 2.23606797749979
    return int(phi**n/sqrt5 + 0.5)

n = 71
print(list(fast_fib(x)-binet(x) for x in range(n)))

it works for n from 0 to 70

@LeakyNun So you should probably add a new special case if n < 71: return binet(n)

Yes, thanks

Binet: time: 0.03 memory: 9984 signal:0

Storing the first n fibonacci values would be faster, but probably way too long, and a cache is probably not needed becuase you usually don't need to use fibonacci that much

Matrix: time: 0.02 memory: 9936 signal:0

matrix is still faster...

ideone.com/SzrpUJ

ideone.com/akKKOi

Hmm, maybe the float arithmetic is too slow

yep

@LeakyNun Well, you can cache results if you want

You would have to consult @Mego

@Mego is caching Fibonacci results going to be useful? Is the speed improvement worth the tradeoff with memory?

@LeakyNun I know you can't because Binet doesn't go that high, but 0.02 vs 0.03 is completely in the realm of randomness so it'd be best to test more times (since you can't quite test more numbers)

@Sp3000 Would you like to test it for me?

:/ just run it in a loop or something (or use timeit)

doing

@Mego Well, you're the master, so you decide.

Hey @Mrs. Ulr!

ideone.com/SzrpUJ

ideone.com/akKKOi

binet is still slower :(

@Mego Thanks, I think I get it now

Okay, I think I'm going to stop golfing SHA for the day or I'll be stuck here all night :/

# F(2n) = (F(n-1) + F(n+1)) * F(n)
#       = (F(n-1) + F(n-1) + F(n)) * F(n)
#       = (2F(n-1) + F(n)) * F(n)

# F(2n-1) = F(n-1)*F(n-1) + F(n)*F(n)

# this returns [F(n-1), F(n)]
def fast_matrix_pow(n):
    if n==0: return [1,0]
    [a,b] = fast_matrix_pow(n>>1)
    b2 = b*b
    a,b = a*a+b2, (a<<1)*b+b2
    if n%2 == 1:
        return [b,a+b]
    return [a,b]

def fast_fib(n):
    return fast_matrix_pow(n)[1]

ideone.com/EZz9zm

@Mego Pull request

:) Chat ees ded

RIP chat

:/ Chat ees ded

chat.stackexchange.com/…

@MartinEnder ಠ___ಠ

chat.stackexchange.com/…

@flawr ಠ_____ಠ

chat.stackexchange.com/…

@MartinEnder ಠ__________ಠ

you're a clever bot

@MartinEnder I'm not a bot.

...is what a bot would say.

I'M A HUMAN BEING! ಠ____________________ಠ

Do you speak russian?

@MartinEnder Whoever starred that, please correct your stars >_>

Or I will leave this chat forever <_< :P

^ starred

(:p)

v disapproval face

ಠ_ಠ

@Fatalize You're right.

phew

6 days before Euro, prepare to get rekt @zʏᴀʙiɴ101

@Fatalize ಠ_ಠ ಠ_ಠ ಠ_ಠ ಠ_ಠ ಠ_ಠ ಠ_ಠ ಠ_ಠ ಠ_ಠ ಠ_ಠ ಠ_ಠ ಠ_ಠ ಠ_ಠ ಠ_ಠ ಠ_ಠ ಠ_ಠ ಠ_ಠ

if you could beat England though...

Hey @Doorknob!

Making me, a totally not guilty boy, rekt.

@HelkaHomba Years ago I was told I was INTJ by a work test, but the test you linked to gave me INFP-A (mediator). I wonder if this is a difference in the test or a difference in me over time.

I think getting inconsistent results for the MBTI is par for the course.

A lot of it depends on the kind of (social/work) situations you’ve dealt with most recently, your mood, the phrasing/order of the questions…

Yes there were definitely questions where I thought I could answer two very different ways as my response would depend on more context

It turns out I’m one of this place’s many ENTPs! But, I think I’m more like an XNXP.

I feel like a better “personality test” is reading the columns of this image and deciding which way you lean on them

The two that changed (T to F and J to P) are still much nearer 50% than the I (81%) and N (99%), so I guess INXX would describe me better

@Lynn That's a handy image to see everything in one place. I do seem to fall into the top right quarter rather than one box in particular

@flawr We already seen it ~4-5 days ago. >_>

But still, lol

@zʏᴀʙiɴ101 I've seen it today. <_<

>_<

I hadn't seen it, and it made me laugh, and you're still contributing far less noise than some others :P

^

I've become less annoyed by reposts with the realization that not everyone has seen it yet. In particular, I've seen a lot of such things only because it was a repost.

Another one I finally found:

reddit.com/r/Welding/comments/3usm4k/…

Job title: "Submarine nuclear power plant emergency welder"

The other chat room I frequent suffers from too little noise

@trichoplax ......yeah. A whole month of posts (almost exclusively by a bot) on one page is...yikes.

I think the main site will need to grow more before chat picks up (even TNB only has a tiny proportion of PPCG's population), but I also wonder if it just needs a small conversation to get going before it becomes self sustaining

This edit suggestion

codegolf.stackexchange.com/review/suggested-edits/30860

Spam?

Python 72 will be adopted sooner than Python 3

@EᴀsᴛᴇʀʟʏIʀᴋ Spam usually means promoting something. Unless that includes promoting chaos I don't think spam is the word for it :)

I like to check the post in context in case of little things like this...

@trichoplax Which room?

The cornell box

Yes, TCB. Computer Graphics is still a fledgling site so chat is very quiet

Wowowow, I hit 15k reputation!

nice!

top 2% apparently also

@Lynn congratulations!

@Lynn May I ask, are you male/female? Just asking as Lynn is usualy a female name.

nsfw

but funny

@Lynn nice.. .empty website?

Yes! Hosting is expensive, and I don’t know what I want to do with foldr.moe yet ^^

Right now, though, [email protected] is a cute email address.

@Lynn are you doing a Ph.D. since 2016?

(It just redirects to my more boring Gmail one.)

Whoa, I’m not doing a PhD, no

Why?

searching Lynn + name of your university shows a women that does

Probably because you should.

^ too

Aw. °v°

Well, Lynn is a common name here. Apparently it’s rare/unusual in the Anglosphere

@Lynn ... @AlexA.? What are you doing being an emoticon that isn't >:U????

@Lynn commonish near me?

@Lynn make it a repository of moe images

behindthename.com/top/lists/netherlands/2015 Look at that sweet 13th spot

> bram

+1, is prime.

^

@EᴀsᴛᴇʀʟʏIʀᴋ Idea: 50% 萌え, 50% Moe Szyslak

@EᴀsᴛᴇʀʟʏIʀᴋ That's not Mego?

And fibbonacci.

@MᴀʀsUʟᴛᴏʀ alex to me.

Also unlucky to Christians

@flawr and fibbonacci, emirp, and happy.

@MᴀʀsUʟᴛᴏʀ not really

more unlucky to gamblers

Unlucky to superstitious hotel elevators

@MᴀʀsUʟᴛᴏʀ The number 13? I never considered that to be a Christian superstition. In fact, I don't think of it as any specific religion's superstition.

@El'endiaStarman But doesn't it as it is now originate from the Christian Last Supper?

@Lynn Fleur doesn't sound very Dutch

not dutch iirc

belgian

@MᴀʀsUʟᴛᴏʀ I don't think so.

@MᴀʀsUʟᴛᴏʀ Huh, perhaps? Research time!

@EᴀsᴛᴇʀʟʏIʀᴋ "Most Popular Names for Births in the Netherlands 2015"

I linked the Netherlands one, because it’s especially common there. But Flanders is like the B-side to the Netherlands

@El'endiaStarman Also the fear of Friday the thirteenth

Still doesn't explain why Dutch people call their daughters Fleur

Also, I should really be looking at the 1996 lists, I guess

@MᴀʀsUʟᴛᴏʀ wikipedia and co. say nobody has a clue, but that could be one reason.

Oh

The Last Supper is one possible reason, but none of the possibilities are regarded as particularly likely.

Elon Musk thinks we are characters in a video game

^ another claim with stupid assumptions

doesn't believe Musk

^

Just posting for fun.

I mean, sure, a lot of people accept that theory, but I think it would be #2

I don't think very many people want to watch a universe simulation at all. Also, an entire universe is a lot to simulate.

Seems to me just like another variant of solipsism.

My response is generally, "What difference does it make? None." and I proceed to live my life in exactly the same way I did before.

^ don't want to start another debate but you could say the same thing for religion

@NewMainPosts unclear, but good idea

@Fatalize How about french?

@flawr as far as I know Dutch is not French

I do not know any dutch, so I cannot say.

it's like a mix between English and German

kinda

IK BEN FLAWR

VOEDEN VLIEGTUIG NAAR ME

^ not very pretty

@Fatalize Huh, really? I wouldn't say so for near any religion. Take Buddhism, for example. You have an incentive to live better so that you get closer to achieving enlightenment, through however many lives it takes. With this "we're just a simulation" theory, none of this is real. Elon Musk thinks he's an artificial construct, yet he works incredibly hard to ensure humanity's long-term survival. That seems to me to be a huge disconnect between belief and action.

'course, many religious people also have a disconnect between belief and action, but not quite so fundamentally, methinks.

sure, but if that theory of simulation said that the first person to go to pluto gets to live outside the simulation, people would start projects to reach Pluto

I hoped methink is an official verb.

so in short there's 0 difference between this theory and any Religion, beside the made-up benefits it supposedly provides after life

Somebody starred my dutch message? Did they translate it?

@flawr it is iirc

FEEDING PLANE TO ME

@EᴀsᴛᴇʀʟʏIʀᴋ I was able to (quite accurately) guess what it means by combining the languages I know=)

:D

@Fatalize nope

i just don't get the point of view of "I need an incentive to live better"

supposed to be FEED CRASHING PLANE TO ME

The crashing is missing?

hm

If anything it's more hypocritical to do "good actions" because if you don't then you go to hell, instead of doing "good actions" because you feel like it

anyway

can a mod eleven CRASHEN in between the first 2 words for me?

why do I start those stupid debates every time :p

@trichoplax you have fancy mod powers, right?

@Fatalize because you are fatalize

@Fatalize look there is religious people here so I don't think you should start a debate here

That is why I strive to be the most evil person I can be (as long it is not too artuous and I do not have to get up from the couch).

@LeakyNun it's happened many many times before

@flawr do you suscribe to reddit r/watchpeopledie or something?

^^ and way worse than this

@Fatalize Certainly, but does anyone say that? Relatedly, you could consider the theory of simulation to be its own religion, since it's a strongly-held belief with (almost) zero supporting evidence, which seems to me to be the way that most atheists and agnostics view religions.

^^

@El'endiaStarman pls no start teh fightz

(And mr starman is certainly not the worst discussion partner.)

Also, debates and/or discussions aren't bad, intrinsically. It depends on the people.

we need a debate room

All of you are wrong.

^ especially you

^

@Geobits Nope, only Alex.

Nope

He is TRYING TO CONFUSE US WITH HIS WRONGNESS RUN

Alex is just the example we use.

everyone-is-wrong

Alex is a theoretical Oracle that generates wrong information

@Fatalize I've seen this viewpoint before, and I do think there is a grain of truth to it. An important thing to consider, though, is why some religious person X is doing good things. If it's in fear of punishment, then yes, it's much like you describe. If it's in expectation of reward, not so bad. Best is doing good things because it's right, and getting a reward as a side benefit, which is the attitude I try to have.

@El'endiaStarman But you don't have to be religious to know that it's right though. You have to be if you fear or expect a reward

Something I still haven't wrapped my mind around is "Why do good things if none of it matters in the end?" What's your response to that?

Who says it doesn't matter? Just because there's no afterlife doesn't mean you leave no impression on the world.

It matters to the person you do good to

which makes the world a better place, just slightly

I'm referring mostly to the eventual death of the universe.

and a better world is better for yourself to live in

@Quill 10/10 would pet that cat again

@El'endiaStarman lol

@Quill Bahaha. "Gee, I can't fit myself through this going forward, so I'm gonna go sideways and face-down, and that'll work!"

@El'endiaStarman I think that's taking it a bit too far. You could make that argument about literally anything. "Why get out of bed? The universe is just going to die in X years."

People need comfort.

to the extent that they believe in things without evidence just to feel better

Depending on the philosophy you ascribe to, there are plenty of non-religious reasons to do good things. Altruism, selfishness, etc.

@Fatalize What does "religious" mean to you? I might be interpreting it as something else.

Yes, but religious people find the religious reason to be the most convenient

@Geobits Ha, point. However, getting out of bed is not quite on par with making the world a better place.

It could be. Depends on the reason I'm getting up :P

haha, sure

@El'endiaStarman People that believe in "organized" belief systems that are not disprovable. I don't have any problem with people that think a god exist, I have a problem with people who write rules or "recommendations" based on that assumption

I don't even mind the rules or recommendations. If you want to keep to those rules that is. I may not.

I mind them

cause people impose them on their children

@Fatalize like me :/

http://i.stack.imgur.com/s7unq.gif

@Mego Actually, yes.

@Fatalize People impose any manner of rules on their children, religious or not. Part of growing up is deciding how much of your parents' rules are bullshit, and which ones were worth the discipline.

@Fatalize so its wrong to teach my children what I believe? What do you teach your children? Fatalism (pun intended)? Follow your sinful human desires and they will do you good?

^^

not politics right now, but whatever

^

@Geobits Imposing rules and manners is perfectly fine if they are not based on ridiculous assumptions

@Fatalize How is that?

you don't need to assume a god exist and wants you to do good to teach your child not to steal

@Fatalize yeah, I can't see how anyone can believe in god with more than a 51:49 descision

@Geobits Some of those rules make the world a worse place

I understand @BaldBantha's point if it one was certain

What if they're based on no/invalid assumptions?

@EᴀsᴛᴇʀʟʏIʀᴋ I vastly prefer a civilized discussion about contentious topics (which this is) to pointless, noise-filled discussions about avocad or whatever.

okay. I disagree, but whatever.

@LeakyNun To your eye, yes. I'm sure some people would argue that you live a terrible life as well. Morality is subjective imo.

@Geobits But the harm that those rules bring is objective.

@BaldBantha One example, teaching abstinence to your child does way more harm than good generally, because they will very commonly end up "sinning" anyway, but have no idea about safety

@LeakyNun Right, but that isn't about religion exactly. It's about stupid rules. You can find stupid rules springing from any number of sources.

@BaldBantha I have a question for you: are you 100% certain that god exists, or is it more of a 60% 40% thing?

@BaldBantha Teach your children to question what you believe instead of what you believe.

@EasterlyIrk Politics and personal beliefs are only bad discussions to have when people take comments personally, I wouldn't worry too much, the mods can handle that conflict if it arises :)

Take helicopter parents, for example. They maintain strict rules for their children, to "make them better". It often ends up harming them psychologically and socially, but there's no religion component.

It will be way worse when they announce that Clinton is nominated instead of Bernie

@Maltysen 100%

hides

Besides, pascal's wager

@Quill Just FYI, that doesn't ping me. But okay.

Doesnt matter.

@BaldBantha Fear of the unknown.

@EᴀsᴛᴇʀʟʏIʀᴋ That's why small caps are bad

@BaldBantha yes, but multiple religions exist

@Fatalize unhides and calls for the wrath of alex

Pascal's wager is the worst.

^

@BaldBantha Pascal's Wager is more of an argument against the lack of an afterlife than anything else.

^^

@BaldBantha that doesn't look good

Probably better than crystal skull.

why not wager for Pastafarianism

@Fatalize @orlp come hear your lord and savior being discussed

@BaldBantha what makes you so sure about god?

@Maltysen and Christianity IMO is the most backed with inteligent proofs and holds up to what you may throw at it

*With enough twisting

@BaldBantha I understand why someone would choose to believe in a particular religion, but what makes you 100% sure

@BaldBantha "intelligent proof" demonstrate some.

@El'endiaStarman How do you justify that some parts of the Bible are supposed to be interpreted and some parts should not? e.g. why don't Christians interpret god as "Nature", even though they interpret the "7 days" thing? I never understood that

If the validity of Christianity specifically is going to be discussed, then take it here:

@El'endiaStarman (Un)surprisingly, Christianity.SE is not a bunch of Christians.

@LeakyNun read C.S. lewis Mere Christianity. Let's take this into the upper room btw

@LeakyNun Huh?

@El'endiaStarman I thought you're a mod there

@LeakyNun Yes, I am a mod on C.SE.

@LeakyNun it is christians and catholics?

@EᴀsᴛᴇʀʟʏIʀᴋ No, they're neutral there.

?

Well, El'endia should know more than me.

?

what are you trying to say though?

neutral?

They're just discussing about Christianity.

They don't have to be Christians.

In its earliest days, Christianity.SE adopted the standard that any group who calls themselves "Christian" is Christian for the purposes of the site.

So like Christian Slater?

I guess technically he's a group of one.

...

@El'endiaStarman so you consider scams like scientology christian?

They can probably post questions and stuff, but downvotes can be used freely as @Geobits has demonstrated.

It's hard to differentiate. You could easily have the opinion that any religion is a "scam".

^

Life is a scam.

you don't get your money back when somebody tricks you into buying 43 watermelon poptarts

(any haskellians here? i have a problem)

@Fatalize Scientologists actually don't call themselves Christian!

@flawr @Lynn you still here?

xnor also knows haskell iirc

and @Zgarb I think

@MartinEnder do you only know mathematica and python (apart from other esoteric languages)?

@JesterTran I just saw an ad on Stack Overflow, that led to your anagram business sister. o_O

Umm. Did Chrome just change its icon set, or is it just me? (back/refresh/home/etc)

@Geobits It's not just you. Chrome did change its design.

@EᴀsᴛᴇʀʟʏIʀᴋ I don't know Python all that well actually. But I do know some Ruby, JS, C, C++, C# as well as basics of a few other languages (like Java, Matlab, Julia, and probably a few I can't think of right now).

@EᴀsᴛᴇʀʟʏIʀᴋ Anyone can post and answer questions, but they must be about some Christian group, where "Christian" means "any group that calls itself Christian". It's worth noting that basically nobody believes that all such groups are actually Christian.

okay to both

@EᴀsᴛᴇʀʟʏIʀᴋ that's not a scam >_>

is too BUT POPTART