RE: Find maximum value of recursively-defined "fusc" function

Question

Continued from the previous post - a brute-force approach to calculating all the vectors from 0 to n.

I've come up with yet another solution, after I've realized that the vector takes up too much memory. But it is still not satisfactory, and is quite slow to the point that it is noticeable even on my local machine. I know that this code can be made in such a way that it only requires one for-loop, but I am not sure on how to implement that.

#include <math.h>
#include <vector>
#include <algorithm>
#include <iostream>
int main() {
 uint64_t number, leastMultipleOf2, powerOfTwo, maxFusc;
 std::vector<uint64_t> saveVector = {1, 2, 1};
 std::cin >> number;
 if (number==0 || number==1) {
 maxFusc = number;
 } else {
 powerOfTwo = floor(log2(number));
 leastMultipleOf2 = pow(2.0, powerOfTwo)/2;
 saveVector.reserve(leastMultipleOf2+1);
 for(int i=1; i<powerOfTwo; i++) {
 maxFusc = *max_element(saveVector.begin(), saveVector.end());
 for(int j=1; j <= (2*pow(2.0, i))-1; j+=2) {
 saveVector.insert(saveVector.begin() + j, saveVector[j-1] + saveVector[j]);
 }
 }
 maxFusc = std::max(maxFusc, *max_element(saveVector.begin(), saveVector.begin()+(number-(2*leastMultipleOf2)+1)));
 }
 std::cout << maxFusc << std::endl;
}

What improvements can be done on this snippet of code?

• Quuxplusone: It's worth mentioning that fusc is Stern's diatomic series, A002487, and so it would not be surprising to find that there was a well-known closed form for the answer. See "The amazing 'fusc' function" (Rob Hubbard, April 2013).

Answer 1

Prefer the C++ header <cmath>. This puts the relevant functions into the std namespace.

Talking of namespace, several other identifiers are used without the necessary qualification (std::uint64_t, std::max_element).

We use >> streaming without any checking for successful conversion.

We use std::endl when a plain newline would be sufficient.

std::uint64 isn't a required type - prefer one of the guaranteed types unless you need exactly 64 bits.

Don't declare all the variables up front. Prefer to minimise scope, and if possible, declare and initialise in one.

Prefer integer << to std::pow(2.0, x). It's more exact, and faster.

Create a function instead of cramming everything into main().

Why are we examining the entire array with std::max_element() every time around the loop? Do it just once at the end, or update maxFusc as we go.

Whilst we can reason about this particular sequence to come up with a faster method, I got several hundred times speedup simply using the obvious approach of computing each value from its previously-calculated dependent values:

#include <cstdlib>
#include <iostream>
#include <vector>
using Number = std::int_fast64_t;
Number max_fusc(Number n)
{
 if (n <= 1) {
 return n;
 }
 std::vector<Number> cache(n);
 cache[1] = 1;
 Number max{0};
 for (Number i = 2; i < n; ++i) {
 cache[i] = cache[i/2] + i % 2 * cache[i/2+1];
 if (cache[i] > max) {
 max = cache[i];
 }
 }
 return max;
}
int main()
{
 Number number;
 std::cin >> number;
 if (!std::cin) {
 std::cerr << "Invalid input\n";
 return EXIT_FAILURE;
 }
 std::cout << max_fusc(number) << '\n';
}

• Toby Speight: Perhaps the online challenge has other constraints - a common one is that it wants the results modulo some other number (often 1'000'000'007, I think).
• Toby Speight: If you want to evaluate the function for larger values, then we need to use more of the properties of the function. Works fine here with 108 as input (giving result 317811) but larger values obviously require more memory for the result cache.
• vnp: The constraint given by SPOJ is \$n \le 10^{15}\$. Paired with the memory limit of 1536 MB it effectively prohibits any cache-based solution.
• Toby Speight: Thanks for the extra information @vnp. Shame that wasn't mentioned in the question.
• Davislor: The fixed-width types will stop being optional in C23. Still are in C++, as you said. (For now.)

Answer 2

Verify that input was successful:

Change:

std::cin >> number;

to:

std::cin >> number;
if (!std::cin) {
 std::cerr << "Error: invalid input.\n";
 return EXIT_FAILURE; // <cstdlib>
}

Or:

if (!(std::cin >> number)) {
 std::cerr << "Error: invalid input.\n";
 return EXIT_FAILURE;
}

Answer 3

Given the constraints not mentioned in the question (namely that input may be as large as 1015 and memory use is limited to 11⁄2 GB), this loop is not the way to approach this problem:

 for(int i=1; i<powerOfTwo; i++) {

Instead, we'll want to find ways to determine the maximum value by examining the properties of the sequence. It probably helps to consider the binary representation of numbers, given the importance of dividing by two to the definition of the function.