At least the sum needs ~log(N^2) bits. We typically assume that stuff fits in the native word size and thus takes a single cycle independent of the actual lengt

At least the sum needs ~log(N^2) bits. We typically assume that stuff fits in the native word size and thus takes a single cycle independent of the actual length of the number, but that's obviously not actually true (for numbers >= 2^32 or 2^64, etc.)