This fizzbuzz competition specifically requires the solution to work up to 2^63 which is not possible as the largest int in JS is 2^54-1. You would have to use BigInt which would greatly reduce your performance.
I'm not a programmer just a pedant ... can't you just concatenate two integers one as your bigend and one as your little end. Sure, probably not fast, but slow !== impossible.
This has piqued my interest, I'm slightly familiar with C and Python, do you (or does anyone) know of any sort of review of resource optimisation for a simple program (like fizzbuzz)?
To me, naively, it seems like the bigend would fit in a register and so memory use wouldn't increase noticeably if you used some sort of double integer type. So it's it processor bound?
That's not native 64-bit integers. That's BigInt, and it's already out everywhere, and unless the situation has changed, it's significantly slower than just 64-bit integers would be.
I'm not actually attacking JavaScript for this, note. I don't think it's really all that much of a problem given the purposes of JavaScript, and I think it could really be better fixed by doing something similar to what Lua did, and have all numbers transparently either a 64-bit floating point number or a 64-bit signed integer. If you are using JavaScript and something like specifically needing 64-bit integers is an issue for you, there's a good chance you should just be using WebAssembly.
I have no idea how one does I/O to stdout in Node, so in the following I'm just going to assume that we have a function printi() that takes an integer argument and prints it, without and padding and without a newline, we have a function prints() that takes a string and prints it, and that we have a function nl() that prints a newline.
Here's a program that would print the numbers from 1 to 9999999999999999999, which is larger than 2^63, without using BigInt.
for (let r = 1; r < 1000; ++r) {
printi(r); nl()
}
for (let l = 1; l < 10000000000000000; ++l) {
for (let r = 0; r < 10; ++r) {
printi(l); prints('00'); printi(r); nl()
}
for (let r = 10; r < 100; ++r) {
printi(l); prints('0'); printi(r); nl()
}
for (let r = 100; r < 1000; ++r) {
printi(l); printi(r); nl()
}
}
That's not yet FizzBuzz but it could be made so by wrapping the print lines with a conditional check to see if they should be replace with Fizz, Buzz, or FizzBuzz. Just keep a variable around the is the current line number mod 15, and use it for the FizzBuzz logic check.
But first let's take a closer look at the "count to 9999999999999999999" program and see if it can be sped up. The first thing to notice is that each time through the outer loop it calls printi(l) 1000 times. Printing integers is often slow so calling printi 1000 times on the same l is not good.
Instead, we should print l to a string at the top of the outer loop, and then prints that string in the inner loops. I'll assume there is an itos() function that takes an integer and return a string.
We could also precompute all the right side strings.
let right = []
for (let r = 0; r < 10; ++r) {
right.push('00' + itos(r) + '\n')
}
for (let r = 10; r < 100; ++r) {
right.push('0' + itos(r) + '\n')
}
for (let r = 100; r < 1000; ++r) {
right.push(itos(r) + '\n')
}
So now the counting parts would look something like this:
for (let r = 1; r < 1000; ++r) {
printi(r); nl()
}
for (let l = 1; l < 10000000000000000; ++l) {
left = itos(l)
for (r = 0; r < 1000; ++r) {
prints(left + right[r])
}
}
Now add in the FizzBuzz logic and put it all together:
let n = 1 // current count % 15
let right = []
for (let r = 0; r < 10; ++r) {
right.push('00' + itos(r) + '\n')
}
for (let r = 10; r < 100; ++r) {
right.push('0' + itos(r) + '\n')
}
for (let r = 100; r < 1000; ++r) {
right.push(itos(r) + '\n')
}
for (let r = 1; r < 1000; ++r) {
if (n == 0) {
prints('FizzBuzz\n')
} else if (n % 3 == 0) {
prints('Fizz\n')
} else if (n % 5 == 0) {
prints('Buzz\n')
} else {
printi(r); nl()
}
if (++n == 15) n = 0
}
for (let l = 1; l < 10000000000000000; ++l) {
left = itos(l)
for (r = 0; r < 1000; ++r) {
if (n == 0) {
prints('FizzBuzz\n')
} else if (n % 3 == 0) {
prints('Fizz\n')
} else if (n % 5 == 0) {
prints('Buzz\n')
} else {
prints(left + right[r])
}
if (++n == 15) n = 0
}
That's going to be slower than a similar simple FizzBuzz that just goes to 2^54-1, but I don't think it would be a lot slower.
Yes, in theory it could print all the numbers you said, but in practice it won't because of floats dropping precision at some point. For JavaScript that point is 2^53.
The easiest way to see this is by typing `9007199254740992 + 1` in your browser's dev console. It should spit out `9007199254740992`.
`(Math.pow(2, 53) + 1) == Math.pow(2, 53)` returns true.
That means your program would print invalid output (or rather start looping infinitely) starting at that number (which is much smaller than 2^63) thus disqualifying your solution.
When the person I was responding to said the largest JS int is 2^54-1 I assumed that meant I could use all integers in [0, 2^54-1], but you are right that I can only go up 2^53. That breaks the specific code I posted but not the underlying idea. Fixing it to deal with that lower upper bound is easy.
Just change the constant 10000000000000000 in the outer loop to 1000000000000000 (which is 2^49+437050046578688 and well below 2^53), change the filling of the right[] array to
for (let r = 0; r < 10; ++r) {
right.push('000' + itos(r) + '\n')
}
for (let r = 10; r < 100; ++r) {
right.push('00' + itos(r) + '\n')
}
for (let r = 100; r < 1000; ++r) {
right.push('0' + itos(r) + '\n')
}
for (let r = 1000; r < 10000; ++r) {
right.push(itos(r) + '\n')
}
and change the loop that starts "for (let r = 1; r < 1000; ++r) {" to go to 10000 instead of 1000.
> That's going to be slower than a similar simple FizzBuzz that just goes to 2^54-1, but I don't think it would be a lot slower.
OK, I've actually tried it, after fixing the issue Allypost identified with the original code (JavaScript integer arithmetic only works up to 2^53, not the 2^54-1 I had assumed).
Here's a simple FizzBuzz:
let n = 1
for (let r = 1; r < 9990000; ++r) {
if (n == 0) {
console.log('FizzBuzz')
} else if (n % 3 == 0) {
console.log('Fizz')
} else if (n % 5 == 0) {
console.log('Buzz')
} else {
console.log(r)
}
if (++n == 15) n = 0
}
I compared that to the the more complicated one, with the outer loop changed to just go to 999, so it would produce the same output as the simple FizzBuzz. (And with the more complicated one changed to use console.log for output instead of the dummy functions in the original, itos() replaces by letting JavaScript implicitly do the conversion, and getting rid of explicit newlines since console.log works in lines.
Running each a few times via node with stdout directed to /dev/null, the simpler might be slightly faster but there is enough variation run to run that there is overlap. E.g., I got 23.811 vs 23.979 when I ran the two once, and then 24.325 and 25.550 when I ran them again.
Similar relative results when directing output to a file. There I actually saw in most runs the complex one run slightly faster than the simple one, but there was enough variation that I can't really say that one was on average faster than the other. The runs saving to disk took about 2.3x as long as the ones that discarded output.
None of them were anywhere near the speed of the programs in other languages on the code golf page linked a fews comments upthread. We're looking at about 5.4 MB/second when not saving the output to disk. That's around 1/20th the speed of the slowest on on the code golf page.
I'm just running things with "node file.js". I don't know if there are options that could be set to make it faster.
Anyway, the assertion upthread that JavaScript is not fast for this seems plausible, though not for the reason given (that it would need BigInt).
