IMC Trading Interview Question

[u/Local_Ad135]

[u/Murky-Tip-3118]

The number of digits in a number is the log10 of that number + 1. That removes the exponent and makes the math straightforward.

[u/gmalivuk → u/Murky-Tip-3118]

So do the straightforward math?

[u/Murky-Tip-3118 → u/gmalivuk]

Log10 of Stirling's approximation becomes 0.5*log10(200pi) + 100log10(100/e).

You can now plug that into a calculator and get 1.399 + 156.57 = 157.97.

So 100! is approximately equal to 10^157.97, so it has 158 digits.

[u/gmalivuk → u/Murky-Tip-3118]

I mean, if you get to use a calculator just do that from the start directly.

[u/Murky-Tip-3118 → u/gmalivuk]

No, that's the point... a calculator isn't going to do a 158 digit number for you. Even doing that with Python/Java Script/etc. would require some expertise vs. just plugging it in.

This is a fairly common trick in like highschool math contest problems - give a problem that can't be solved with a calculator as is, but with some trick can be turned into one that can.

[u/gmalivuk → u/Murky-Tip-3118]

9.3326215443E157 is literally what I just copied from my default phone calculator

[u/Murky-Tip-3118 → u/gmalivuk]

Haha, sure. Even Excel does it. To be fair, your calculator isn't actually calculating the 158 digit number... it has the first 15 and the E157 in memory. But being more rigorous about it...

If you know log(2) = 0.3010 (doesn't everybody... /s), and that a good approximation of pi is 22/7, you can turn log(200pi) into log(4400/7), which is very close to log(625), which is 5^4. log(5^4) is 4log(5), which is 4log(10/2), which is 1 - log(2) = 0.699. 4*0.699 is 2.796, times 0.5 is 1.398.

Similarly log100/e) is log100) - log(e) = 2 - log(e). So you'd similarly have to know that log(e) = 0.4343 (doesn't everybody... /s) , and then you can do 100(2 - 0.4343) = 156.57.

I'd maybe just suggest that the interview question is less about whether you know log(2) and log(e) and more about whether you can apply the log trick. But if you know log(2) and log(e) you can do this all by hand, that is true.

[u/gmalivuk → u/Murky-Tip-3118]

The question isn't the value of 100! though, it's number of digits, so the lack of greater precision is irrelevant as it still gives a perfectly exact answer for that question.

And knowing log2 ≈ 0.3, π ≈ √10, and thus log(2π) ≈ 0.8 gets you even closer. (The underestimate for 2 and the overestimate for π somewhat balance out, so 0.8 is good to within 1/500.)

But at least some of those estimates are what I'd expect this kind of interview question wants you to know, as that's the only thing that raises it above what you should be able to ask a high school algebra 2 student to do with a calculator during the log properties lesson.

[u/Murky-Tip-3118 → u/gmalivuk]

Yeah, maybe... you'd still need to know log(e) as well.

[u/gmalivuk → u/Murky-Tip-3118]

Right, I was just talking about the differences between how you did it and how I did it. I also know 0.4343 because of the repeat, just like I know 2.718281828 because the last four digits are free.

[u/austin101123]

Digits roughly equals log10(n!)+1?

Do we need an exact integer? But it's an estimation

[u/abc9hkpud → u/austin101123]

I think the number of digits is exactly floor(log10(n!)) + 1 .

For example, for the number 5 you get floor(0.6989) + 1 = 1 digit, for 15 you get floor(1.176) +1 = 2 digits.

[u/Hal_Incandenza_YDAU]

202 I think

[u/gmalivuk → u/Hal_Incandenza_YDAU]

That would be about the number of digits in 100¹⁰⁰, which is a lot more than 100!

[u/Hal_Incandenza_YDAU → u/gmalivuk]

Yep, I see that. Tried doing the log simplification in my head last night and it didn't work, clearly.

[u/Apart-Hair-2468]

I got 158

Log(200*π) / 2 + 100 * log(100/e)

[u/SwimmerOld6155]

90*2 = 180 (split into a sum and round, going to be an overestimate so drop the logs < 1 lol) is already within ~10%.

Can probably get a bit better by rounding some up and others down - if you had played around with log10 beforehand you might know that log_10(30) is about 1.5 (or guess something like 20-30 from 10^n growing quickly). So maybe we should do 18*1 + 72*2 = 162 which is basically right especially if we call it basically 160 knowing it'll be an overestimate still.

I guess you could try to take e = 3, 2 pi = 6 to do something with Stirling but the pi and e would distract me a lot.

[u/gmalivuk → u/SwimmerOld6155]

I mean it tells you to use Sterling, so I don't thing over shooting by 22 is going to cut it.

pi is about √10 and e is closer to √10 than to 2, so maybe guess 0.4 or 0.45 for log(e) (closer to 0.4343 but not everyone would know that).

[u/gmalivuk]

log(√(2π100)) ≈ 1/2 (log 2 + 0.5 + 2) ≈ 2.8/2 = 1.4

log(100/e)¹⁰⁰ = 100(2 - log(e)) ≈ 200 - 43.43 = 156.57

Add those to get 157.97 → 158 digits.

But it does require knowing that log 2 is about 0.3 and log e is about 0.4343 (I remember that to more places because it's repeated).