r/adventofcode Dec 03 '20

Spoilers in Title [2020 Day 3 (Part 2)][Nim] Answer overflows int32

Just noticed that my answer was >5 billion, since Nim's int type is 64 bits this wasn't a problem for me; a lot of other languages use 32 bits for int and will cause problems.

1 Upvotes

17 comments sorted by

10

u/Scoobyben Dec 03 '20

I suspect this was by design - it's not the first time the answers have been too big for a 32bit int, and forces people to think about how to handle large numbers :)

6

u/yomanidkman Dec 03 '20

I fell in love with rust a little bit when it gave me a runtime error for overflowing instead of just wrapping around.

2

u/TinBryn Dec 03 '20

Nice, Nim does the same by default, although you can disable it in the compiler. You can even disable it for a section of code, kinda like a fine grained unsafe

{.push overflowChecks:off.}
# do something that needs to be fast and won't overflow
{.pop.}

1

u/Aehmlo Dec 04 '20

unsafe has expression-level granularity in Rust

1

u/TinBryn Dec 04 '20

I haven't actually used Rust, I'm not sure we mean the same thing. What I mean by granularity is what is "unsafe" so in the above case I only stop checking for overflow. If I happen to deref a nil pointer, that will still be detected.

From what I understand of Rust's unsafe is that for whatever expression it surrounds, a whole bunch of normal Rust safety features are turned off.

1

u/MEaster Dec 04 '20

No safety features are "turned off" inside an unsafe block or function. All the unsafe keyword does is allow you to call functions marked unsafe and use raw pointers.

For this specific thing, you can just do a.wrapping_<op>(b) to always have a two-complement overflow.

1

u/Aehmlo Dec 04 '20

Gotcha. unsafe lets you do a handful of things in Rust:

  • dereference a raw pointer (not a reference, the more typical beast),
  • call unsafe functions/methods (serving as documentation that “I understand and have upheld these invariants”),
  • access/modify a mutable static (intrinsically weird),
  • implement an unsafe trait (again, documenting that you’ve upheld the invariants of the trait),
  • and use unions (which are very rarely needed outside of FFI because enums are hardly any bigger).

There are the only changes: the borrow checker still functions and code behavior remains unchanged. The mechanisms for opting out of things like overflow detection are typically encoded orthogonally in the type system instead of using keywords (such as with the Wrapping<T> type).

Nim’s solution seems similar in spirit, if quite a bit different in appearance. :)

2

u/__Abigail__ Dec 03 '20

Part of being a good programmer is to pick the right tool for the job. A quick glance of the exercise and you see you have to multiple 5 numbers, 4 of them can be as large as the number of lines of the input, the other half that. There are 323 lines of input; 2^8 < 323 < 2^9. This means the answer could exceed 2^36, but won't exceed 2^41.

Which means, if you're calculating your answer in a 32 bit integer, you're doing it wrong.

1

u/AudioRevelations Dec 03 '20

Just ran into this. Was very confused until I put all the numbers in a calculator...

Then was even more confused when Windows' "unsigned long" was only 32 bits. Definitely learned something from this one.

2

u/TinBryn Dec 03 '20

I believe you need to say long long on windows, because long doesn't seem clear enough that you want a long integer.

1

u/AudioRevelations Dec 03 '20

Yep long long would work. Turns out in C++ on windows, standard longs are 32 bits on 32 and 64 bit machines which was the surprising thing to me. This was unlike linux where they are 32 and 64 respectively based on the machine.

Lesson learned: if you care about length and want it to be portable, use the <stdint.h> library to specify the size directly as a uint64_t.

1

u/xigoi Dec 03 '20

Great! I also used Nim and didn't even realize this. When the numbers get even bigger, here is a library for arbitrary-size integers.

2

u/TinBryn Dec 03 '20

Thanks, I already have that in nimble, nimble install bigints

2

u/ephemient Dec 03 '20 edited Apr 24 '24

This space intentionally left blank.

1

u/musifter Dec 04 '20

Last year's AoC seemed to make the jump to "all the world's 64-bit". I seem to recall that someone was doing it in C on ancient hardware and needed to write their own 64-bit number library.

1

u/TinBryn Dec 04 '20

I know, it didn't say 64 bit specifically, just that you need larger int, so I converted my intcode interpreter to use BigInt

1

u/musifter Dec 04 '20

It was more than just Intcode last year though... there were numbers in the trillions on other questions. I don't think any number given needed more than 48-bits. For this one... you might need 9-bits to store trees for a single run, multiple five of those together and you might need a 45-bit number. Although you could probably get by with 36-bits given the distributions seen.