Вычисление чисел, для которых требуется тип данных размером более 16 байт в C++

Я работаю над функцией для вычисления чисел Фибоначчи и возврата младшей цифры этого числа на C++. Я обнаружил, что в C++ самым большим типом данных является __uint128_t, что дает мне 16 байт для работы. Я написал перегрузку для обработки потоковой передачи __uint128_t. Это вычислит до 186-го числа Фибоначчи, а затем переполнится до 187. Мне нужно подняться намного выше 186. Это моя функция:

__uint128_t get_fibonacci_last_digit_fast (int n)
{
    __uint128_t f[n];

    f[0] = 0;
    f[1] = 1;

    for (int i = 2; i < n + 1; i++)
    {
        f[i] = f[i - 1] + f[i -2];
    }

    return f[n] % 10;
}

Мне известна библиотека boost и другие библиотеки, которые помогают обрабатывать большие данные на C++, но эта функция предназначена для задания, которое необходимо отправить автооценщику, у которого эти библиотеки не установлены. Существуют только стандартные библиотеки C++, поэтому мой код не компилируется при отправке с этими библиотеками. Я рассматриваю возможность создания типа данных для решения этой проблемы. Мы будем очень признательны за любые указания и помощь в продвижении вперед.

Небольшое примечание: вы используете VLA (массив переменной длины), который не является частью стандарта C++.

Chris 20.06.2024 03:18

«Последовательность Фибоначчи — это ряд чисел, где каждое число представляет собой сумму двух предыдущих чисел». -- возможно, я ошибаюсь, но такое ощущение, что вам не нужны полные числа: вас не волнуют старшие цифры...

Christian Stieber 20.06.2024 03:19

Если вас беспокоит только единичная цифра, вы можете применить по модулю к каждому f[i]. И вам больше не нужен «большой» шрифт.

Jarod42 20.06.2024 03:20

Зачем вы вычисляете все число, если вам нужна только последняя цифра? Просто используйте обычный int и на каждом шаге обрезайте все цифры, кроме последней, например. f[i] = (f[i-1] + f[i-2]) % 10; Вы будете выполнять намного больше % операций, но целочисленная точность больше не будет проблемой.

Tom Karzes 20.06.2024 03:20

Доступ к f[n] недействителен и выполняется дважды (последняя итерация цикла и оператор возврата).

Computable 20.06.2024 03:29

Кроме того, здесь нет необходимости в массиве; все, что вам нужно, это два последних значения. sum = f0 + f1; f0 = f1; f1 = sum;.

Pete Becker 20.06.2024 03:30

Существуют только стандартные библиотеки C++. Однако имейте в виду, что автооценщик, похоже, принимает нестандартные типы C++, такие как __uint128_t, и нестандартный синтаксис C++, например __uint128_t f[n]. Итак, ваш автооценщик не такой стандарт C++, как вы думаете.

PaulMcKenzie 20.06.2024 03:39

Также укажите один язык. Вы используете C или C++?

PaulMcKenzie 20.06.2024 03:44

Пожалуйста, не отмечайте несвязанные языки.

ikegami 20.06.2024 03:52

«Я обнаружил, что в C++ самым большим типом данных является __uint128_t». Вам следует изменить «в C++» на «в реализации C++, которую я использую» (и, возможно, указать свой компилятор/инструментарий), поскольку __uint128_t не стандартный C++. (Двойное подчеркивание 🔁 подразумевает это.) Стандарт C++ гарантирует только целые числа длиной не менее 8 байт (long long).

JaMiT 20.06.2024 03:56

В стандартном C++ самые большие целочисленные типы (long long, unsigned long long и (C++11 и более поздние версии) типы фиксированной ширины, такие как std::uint64_t, std::uint_least64_t ) гарантированно будут только 64-битными. (Они могут быть больше, но размеры определяются реализацией, и нет никакой гарантии, что какой-либо целочисленный тип будет больше 64 бит). Вместо того, чтобы пытаться найти (нестандартный) больший тип, я предлагаю вам работать со стандартным контейнером стандартного типа (например, std::vector<unsigned long long>) и реализовывать нужные вам операции таким образом, чтобы не зависеть от размера целочисленного типа.

Peter 20.06.2024 07:59

Ни одно упражнение «вернуть результат по модулю некоторого числа» не должно быть решено простым применением % к результату тривиального решения. Смысл этого упражнения обычно в том, чтобы вы выучили (или запомнили) это (a + b) % m == ((a % m) + (b % m)) % m, поэтому вам понадобится только одна цифра каждого числа в серии; понимая, что вам не нужно хранить более двух последних номеров; и обнаружив, что последняя цифра является периодической.

molbdnilo 20.06.2024 08:29

Если вы знаете, что такое __uint128_t, но не знаете, что такое бигнум, вы держите рукоять стрелы не за тот конец.

n. m. could be an AI 20.06.2024 13:05

Спасибо всем за помощь. Большинство комментариев были очень полезными и информативными. Спасибо.

Dwayne St George 22.06.2024 22:08
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
1
14
147
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Если вам нужна только последняя цифра, вы можете использовать точку Пизано:

#include <iostream>

int get_last_digit(unsigned long long n)
{
    n %= 60;

    if (n <= 1)
        return n;

    int prev = 0;
    int curr = 1;

    for (int i = 2; i <= n; ++i)
    {
        int next = (prev + curr) % 10;
        prev = curr;
        curr = next;
    }

    return curr;
}

int main()
{
    unsigned long long n = 10000000000008989ULL;
    std::cout << get_last_digit(n) << "\n";
}

Принты

9

Примечания:

  • Период Пизано для % 10 равен 60. Мы можем вручную перечислять последовательность Фибоначчи по модулю 10, пока не увидим повторение исходного паттерна 0, 1:

0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1, ..., 0, 1

  • Последовательность 0, 1 повторяется после 60 номеров. Следовательно, мы можем использовать предварительно вычисленный массив, чтобы эффективно получить последнюю цифру для n по модулю 60 за O(1) временную сложность:
#include <iostream>

int get_last_digit(unsigned long long n)
{
    const int pisano[60] = {
        0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1,
        5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6,
        5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1};

    return pisano[n % 60];
}

int main()
{
    unsigned long long n = 10000000000008989ULL;
    std::cout << get_last_digit(n) << "\n";
    return 0;
}

Спасибо. Это было очень полезно. Узнал новое из статьи в Википедии. Спасибо.

Dwayne St George 22.06.2024 22:09

Другие вопросы по теме

Введите 'строка | логическое значение не может быть назначено для ввода «никогда» в машинописном тексте
Почему тип int меняет размер в зависимости от архитектуры процессора, а другие типы — нет?
Определение макроса и использование типов данных для поиска абсолютного значения
Аргумент func с массивом смешанных типов (протокол), затем вызовите статический метод протокола
Не удалось преобразовать число с плавающей запятой 64 в число с плавающей запятой 32 в Python
Как перегрузить процедуру, объявленную в абстрактном типе в Фортране?
Разъяснение: «Значение значения определяется типом выражения, используемого для доступа к нему»
Как изменить неопределенный тип как необязательный в машинописном тексте?
Что вызывает синтаксическую ошибку в агрегате расширения Ada для ограниченного типа? Закомментированный сектин получает синтаксическую ошибку
Как преобразовать тип в универсальный тип, фактический тип которого известен в момент преобразования?