4 ms·

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

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. So not impossible but kinda pointless for JS

shakna 4y ago
There's ASM and C answers, without going near BigNum libraries. You wouldn't necessarily have to implement or use a BigNum library.
- Taywee 4y ago
  ASM and C have access to native 64-bit integers. Javascript does not.
  - shakna 4y ago
    Javascript does [0]. Shipping in Chrome v67, and rolling out elsewhere. [0] https://chromestatus.com/feature/5371603852460032 https://chromestatus.com/feature/5371603852460032
    - Taywee 4y ago
      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.
      - nailer 4y ago
        I suspect the parent thought 'native' meant 'inbuilt 64 bit integers' and you thought 'native' meant '64 bit integers in C'.
tzs 4y ago
Note: none of the code below has been tested! 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.
pbhjpbhj 4y ago
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.
- city41 4y ago
  That's pretty much what BigInt is doing for you.
- TJSomething 4y ago
  The thing that was said to be impossible was writing a fast FizzBuzz. Assuming that your reference is C, it kind of is.
  - pbhjpbhj 4y ago
    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?
    - shepherdjerred 4y ago
      https://codegolf.stackexchange.com/questions/215216/high-throughput-fizz-buzz https://codegolf.stackexchange.com/questions/215216/high-thr...

shakna 4y ago

There's ASM and C answers, without going near BigNum libraries. You wouldn't necessarily have to implement or use a BigNum library.

Taywee 4y ago
ASM and C have access to native 64-bit integers. Javascript does not.
- shakna 4y ago
  Javascript does [0]. Shipping in Chrome v67, and rolling out elsewhere. [0] https://chromestatus.com/feature/5371603852460032 https://chromestatus.com/feature/5371603852460032
  - Taywee 4y ago
    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.
    - nailer 4y ago
      I suspect the parent thought 'native' meant 'inbuilt 64 bit integers' and you thought 'native' meant '64 bit integers in C'.

tzs 4y ago

Note: none of the code below has been tested! 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.

pbhjpbhj 4y ago

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.

city41 4y ago
That's pretty much what BigInt is doing for you.
TJSomething 4y ago
The thing that was said to be impossible was writing a fast FizzBuzz. Assuming that your reference is C, it kind of is.
- pbhjpbhj 4y ago
  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?
  - shepherdjerred 4y ago
    https://codegolf.stackexchange.com/questions/215216/high-throughput-fizz-buzz https://codegolf.stackexchange.com/questions/215216/high-thr...