Fizzbuzz

FizzBuzz по-сениорски

31.01.2021 16:07:40 |

Автор: admin

- Добрый день, я на интервью на позицию старшего разработчика.

- Здравствуйте, давайте начнем с небольшого теста, пока я ваше CV смотрю. Напишите программу, которая выводила бы числа от 1 до, скажем, миллиарда, притом если число кратно трем, то вместо числа выводится Fizz, если кратно пяти, то Buzz, а если и трем, и пяти, то FizzBuzz.

Серьезно, FizzBuzz? Задачка для начальной школы, на сениорскую позицию? Ну ладно.

Я достаю свой верный лаптоп, и пишу такой код:

#include <stdio.h>#define LIMIT 1000000000int main(void) {    for (int i = 1; i <= LIMIT; i++) {        if (0 == i % 3) {            if (0 == i % 5) {                printf("FizzBuzz\n");            } else {                printf("Fizz\n");            }        } else if (0 == i % 5) {            printf("Buzz\n");        } else {            printf("%d\n", i);        }    }    return 0;}

Запускаю программу, она себе бежит, но не так чтобы сильно быстро, через 3 с чем-то минуты, после первого миллиона, я ее прерываю и быстренько высчитываю, что весь процесс займет больше двух суток. Да, наверно надо было включить буферизацию, это бы несколько ускорило, но это не спасет, лучше просто перенаправить вывод в файл, что я и делаю, и через 41.5 секунду у меня есть красивенький файл на 7.5 гигов.

- Вам не кажется, что можно побыстрее? - спрашивает интервьюер.

- Да ладно, основное время занимает I/O, 7.5 гигов записать не шутка, даже на SSD.

- А давайте перенаправим вывод в /dev/null.

- Без проблем.

Через минуту:

- Как это 39.5 секунд? То есть весь I/O занимает 2 секунды, а все остальное время мой код?

- Да, так получается. Это не самая медленная реализация, на каждой итерации два сравнения и один printf, я часто вижу вариант с тремя сравнениями и двумя printfами. Для джуниора, я бы сказал, это даже хорошо. А вот для сениора ...

Это было больно, но, пожалуй, заслужено. Ладно, я тебе покажу, кто тут джуниор.

- Сейчас сделаю побыстрее.

- Попробуйте. Только объясняйте, что вы делаете.

- Видите, что у нас тут есть паттерн каждые 3*5, то есть 15 итераций цикла логика полностью повторяется. Тогда можно переделать цикл:

    for (i = 1; i < LIMIT - 15; i += 15) {        printf( "%d\n"          // 1                "%d\n"          // 2                "Fizz\n"        // 3                "%d\n"          // 4                "Buzz\n"        // 5                "Fizz\n"        // 6                "%d\n"          // 7                "%d\n"          // 8                "Fizz\n"        // 9                "Buzz\n"        // 10                "%d\n"          // 11                "Fizz\n"        // 12                "%d\n"          // 13                "%d\n"          // 14                "FizzBuzz\n",   // 15                i, i+1, i+3, i+6, i+7, i+10, i+12, i+13);    }

- Если раньше на каждые 15 чисел у нас приходилось 15 сравнений переменной цикла и два ifа в теле цикла, то есть в общей сложности 45 сравнений, а каждое сравнение это потенциальная проблема с branch predictionом, то теперь одно. Да и вызовов printfа стало в 15 раз меньше. Одна только проблема цикл не дойдет ровно до миллиарда, а только до 999999990 (макс число, кратное 15 и меньшее миллиарда), так что оставим старый цикл, но только для обработки хвоста, то есть последних 10 значений (это практически не влияет на производительность).

После всех изменений получился такой код.

- И что у нас со временем получается?

- Если вывод в файл, то 22.5 секунды, если в /dev/null 20.2

Интервьюер доволен, похоже, чего-то такого он от меня и ожидал. Но зря он про джуниора сказал.

- Я думаю, что это не предел.

- В самом деле? А что тут можно еще оптимизировать?

- Я уменьшил количество вызовов printfа в 15 раз, но при этом сами эти printfы стали тяжелее. Да и вообще printf сам по себе тяжелый, из-за своей мощности это ведь фактически виртуальная машина со своим языком, полным по Тьюрингу, на нем даже крестики-нолики писали. В данной ситуации используется лишь небольшая часть возможностей printf, так что можно его заменить на что-то свое, более легкое:

#define NUM cur += myitoa(num++, cur)#define FIZZ do { memcpy(cur, "Fizz\n", 5); cur += 5; num++; } while (0)#define BUZZ do { memcpy(cur, "Buzz\n", 5); cur += 5; num++; } while (0)#define FIZZBUZZ do { memcpy(cur, "FizzBuzz\n", 9); cur += 9; } while (0)void print(int num) {    static char wrkbuf[CHUNK_SIZE];    char *cur = wrkbuf;    NUM;    NUM;    FIZZ;    NUM;    BUZZ;    FIZZ;    NUM;    NUM;    FIZZ;    BUZZ;    NUM;    FIZZ;    NUM;    NUM;    FIZZBUZZ;    fwrite(wrkbuf, cur - wrkbuf, 1, stdout);}

- Можно, конечно, использовать уже готовую itoa, но это нестандартная функция, не везде есть, да и она слишком универсальная, поскольку поддерживает разные системы счисления, а у нас только десятичная система - упрощаем все, что можно. Ну и, конечно, в главном цикле просто вызываем print(i) вместо длинного printfа.

Получается такой код.

Я подхожу к доске и рисую табличку с результатами запусков:

Вариант	Вывод в файл			Вывод в `/dev/null`
Вариант	Время (сек)	Относ наивной	Относ предыдущей	Время (сек)	Относ наивной	Относ предыдущей
наивная	41.429	1x	-	39.650	1x	-
оптимизация цикла	22.546	1.83x	1.83x	20.151	1.97x	1.97x
отказ от `printf`	12.563	3.30x	1.80x	8.771	4.52x	2.30x

- В принципе на вывод в файл можно особо не смотреть там какое-то время съедается на I/O, и оно плавает, так что лучше ориентироваться на время без I/O.

Я стираю ту часть, где про вывод в файл.

- Итого ускорение в 4 с половиной раза.

Интервьюер смотрит с уважением. Похоже, интервью я прошел, можно сворачиваться, да и интервьюер уже бумаги начинает складывать. Но я еще не закончил.

- Я знаю, как можно еще ускорить.

- Серьезно?

- Абсолютно. Я до этого использовал чисто технические способы ускорения, а ведь можно еще и алгоритмически улучшить. Смотрите, что будет напечатано, когда мы вызываем, например, print(150000001) и следующий за ним print(150000016):

150000001\n150000002\nFizz\n150000004\nBuzz\nFizz\n150000007\n150000008\nFizz\nBuzz\n150000011\nFizz\n150000013\n150000014\nFizzBuzz\n150000016\n150000017\nFizz\n150000019\nBuzz\nFizz\n150000022\n150000023\nFizz\nBuzz\n150000026\nFizz\n150000028\n150000029\nFizzBuzz\n       ^^         ^^               ^^                     ^^         ^^                     ^^               ^^         ^^

- Отличия всего в 16 байтах, а программа всю строку пересобирает с нуля. Можно просто менять байты на месте. Правда, заранее неизвестно, сколько десятичных разрядов надо поменять, так что это потребуется вычислить сравнить два буфера, и определить, где они отличаются. Это, пожалуй, тяжеловатая задача, но у нас есть, я делаю театральную паузу векторные инструкции и интринсики для них!

Я не озвучиваю, но подразумеваю, что джуниор такого бы не придумал. В этот момент понимаю, что интервьюер тоже.

Открываю Intelовскую страницу с интринсиками и нахожу там нужные векторные функции для работы с 16-байтными векторами. У меня тут максимум 10-байтные, но их можно добить нулями до 16, не проблема. И да, 16-байтные вектора это SSE инструкции, никакой AVX-512 тут не нужен, мой 4-летний мобильный проц это точно потянет.

Получаю такой кусок с жирными и вкусными интринсиками:

unsigned int diff = 0xFFFF & ~_mm_movemask_epi8(_mm_cmpeq_epi8(                                  _mm_load_si128((__m128i const *)prev_first_number),                                  _mm_load_si128((__m128i const *)last_number)));unsigned int diff_pos = 16 - _tzcnt_u32(diff);   // number of changed digits

Быстрая проверка flags в /proc/cpuinfo нужные для выбранных мной интринсиков SSE2 (еще со времен Pentium 4) и BMI1 (появился в Haswellах) в CPU есть, все должно работать.

Запускаю тот код, что получился, смотрю уже только вывод в /dev/null и обновляю табличку:

Вариант	Время (сек)	Относительно наивной	Относительно предыдущей
наивная	39.650	1x	-
оптимизация цикла	20.151	1.97x	1.97x
отказ от `printf`	8.771	4.52x	2.30x
переиспользование буфера	4.490	8.83x	1.95x

Еще почти в 2 раза ускорились! А по сравнению с начальным вариантов так вообще почти в 9. Жаль, до 10 раз не дотянул.

- Ну все, наверно теперь уже хватит. Это уже вполне по-сениорски.

Во взгляде интервьюера читается облегчение.

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

Интервьюер, похоже, начинает чего-то опасаться, и старается как-то незаметно переползти на соседний стул, поближе к выхожу из переговорки, но ему сильно мешают подлокотники. Пофиг, не надо было меня провоцировать!

- Я буду выделять каждому рабочему потоку кусок числового поля, и этот поток будет возвращать готовый буфер для своего куска, а главный поток будет печатать эти буферы, соблюдая порядок:

for (int j = 0; j < THREAD_COUNT; j++) {        thread_pool[j].start_num = i;        thread_pool[j].count = NUMS_PER_THREAD;        thread_pool[j].buf = malloc(BUFFER_SIZE);        pthread_create(&thread_pool[j].id, NULL, worker, (void *)&thread_pool[j]);        i += NUMS_PER_THREAD;    }    int active_threads = THREAD_COUNT;    int max = LIMIT / 15 * 15;    for (int j = 0; active_threads; j = (j+1) % THREAD_COUNT) {        pthread_join(thread_pool[j].id, NULL);        fwrite(thread_pool[j].buf, thread_pool[j].buflen, 1, stdout);        if (max - i > NUMS_PER_THREAD) {            thread_pool[j].start_num = i;            pthread_create(&thread_pool[j].id, NULL, worker, (void *)&thread_pool[j]);            i += NUMS_PER_THREAD;        } else if (max > i) {            thread_pool[j].start_num = i;            thread_pool[j].count = max - i + 1;            pthread_create(&thread_pool[j].id, NULL, worker, (void *)&thread_pool[j]);            i += max - i + 1;        } else {            free(thread_pool[j].buf);            active_threads--;        }    }

- У меня двухядерный проц с гипертредингом, так что четыре рабочих потока одновременно будет оптимально, пока главный поток занимается выводом, один рабочий поток не используется, так что в любой момент времени максимум 4 потока активны. Конечно, стоит поэксперементировать с размером куска, который дается на обработку в идеале рабочий поток должен обрабатывать свой кусок ровно за то же время, что главный поток выводит данные, тогда никто никого не ждет, все работают на максимальной скорости.

Проведя несколько замеров, я остановился на кусках по 3 миллиона чисел удобное число, кратное 15, и результат хороший.

Получился такой код.

Запускаю, и обновляю данный в табличке:

Вариант	Время (сек)	Относительно наивной	Относительно предыдущей
наивная	39.650	1x	-
оптимизация цикла	20.151	1.97x	1.97x
отказ от `printf`	8.771	4.52x	2.30x
переиспользование буфера	4.490	8.83x	1.95x
многопоточность	1.748	22.68x	2.57x

- Ну вот, я уменьшил время обработки в 22 с лишним раза. И код получился очень даже сениорский умный алгоритм, многопоточность, интринсики опять же. Как считаете?

Я отвернулся от доски и увидел, что в переговорке я один. Через стеклянную стенку переговорки я разглядел интервьюера, который что-то быстро говорил секретарю, показывая пальцем в мою сторону. Он что, вызывает охрану? Похоже, что мне тут больше не рады.

Я быстро закрыл лаптоп и покинул офис. Почему-то мне так и не перезвонили.

Все тесты делались на Dell Latitude 7480 с i7-7600U 2.8 Ghz, 16 Gb памяти, SSD и OpenSUSE Leap 15.1 с kernelом 4.12.14, каждый тест не менее 10 раз, выбиралось наименьшее значение. При компиляции использовались флаги -O3 -march=native -pthread

Все варианты кода производят одинаковый результат, когда вывод направлен в файл, то есть работают корректно. Код доступен в этом репо.

Подробнее..

Категории: Интервью , Fizzbuzz , Ненормальное программирование , C , Высокая производительность , Оптимизация , Собеседование , Си

Functional FizzBuzz на Scala

13.06.2020 22:23:27 |

Автор: admin

FizzBuzz это известная задачка, шутливо или не очень задаваемая на собеседованиях, существует множество вариантов реализации даже для такой простой игры. Существует даже шедевры вроде FizzBuzzEnterpriseEdition.

Предлагаю вашему вниманию еще один вариант, не совсем пятничный, а скорее субботний: FizzBuzz на Scala, functional style.

Задача

Для чисел от 1 до 100 нужно выводить на экран

Fizz, если число делится на 3;
Buzz, если число делится на 5;
FizzBuzz, если число делится и на 3 и на 5;
в противном случае само число.

Решение

Программист должен не столько решать задачу, сколько создавать инструмент для ее решения

Начнем с делимости

def divisibleBy(n: Int, d: Int): Boolean = n % d == 0divisibleBy(10, 5) // => true

Нет, это нас не устроит ведь делимость это свойство не только чисел типа Int, опишем делимость в общем виде, а за одно сделаем ее инфиксным оператором (Тут и далее используются некоторые возможности библиотеки cats):

import cats.implicits._import cats.Eqimplicit class DivisionSyntax[T](val value: T) extends AnyVal {  def divisibleBy(n: T)(implicit I: Integral[T], ev: Eq[T]): Boolean = {    import I._    (value % n) === zero  }  def divisibleByInt(n: Int)(implicit I: Integral[T], ev: Eq[T]): Boolean =    divisibleBy(I.fromInt(n))}10 divisibleBy 5 // => trueBigInt(10) divisibleBy BigInt(3) // => falseBigInt(10) divisibleByInt 3 // => false

Тут используются:

type class "Integral" требующий от типа "T" возможности вычислять остаток от деления и иметь значение "zero"
type class "Eq" требующий от типа "T" возможности сравнивать его элементы (оператор "===" это его синтаксис)
расширение типа "T" с помощью extension methods & value classes, которое не имеет рантайм-оверхеда (ждем dotty, который принесет нам нормальный синтаксис экстеншен методов)

Строго говоря метод divisibleByInt не совсем тут нужен, но он пригодится нам позже, если мы захотим использовать литералы целочисленного типа 3 и 5.

FizzBuzz

Отлично! Перейдем к вычислению того, что нужно вывести на экран, напомню, что это может быть "Fizz", "Buzz", "FizzBuzz" либо само число. Тут есть общий паттерн некоторое значение участвует в результате, только если выполняется определенное условие. Для этого подойдет Option, который будет определять используется значение или нет:

def useIf[T](value: T, condition: Boolean) = if (condition) Some(value) else None

Как и в случае с "divisibleBy(10, 5)" и "10 divisibleBy 5" задача решается, но как-то некрасиво. Мы ведь хотим не только решить задачу, но и создать инструмент для ее решения, DSL! По-сути, большая часть работы программиста и есть создание DSL разного рода, когда мы отделяем "как сделать" от "что сделать", "10 % 5 == 0" от "10 divisibleBy 5".

implicit class WhenSyntax[T](val value: T) extends AnyVal {  def when(condition: Boolean): Option[T] = if (condition) Some(value) else None}"Fizz" when (6 divisibleBy 3) // => Some("Fizz")"Buzz" when (6 divisibleBy 5) // => None

Осталось собрать все вместе! Мы могли бы использовать orElse и получили бы 3 правильных ответа из 4, но когда мы должны вывести "FizzBuzz" это не сработает, нам нужно получить Some("Fizz") ? Some("Buzz") => Some("FizzBuzz"). Просто строки можно складывать, но как сложить Option[String]? Тут на помощь нам приходят ~~монады~~ моноиды, cats предоставляет нам все нужные инстансы и даже удобный синтаксис:

  def fizzBuzz[T: Integral: Eq: Show](number: T): String =    ("Fizz" when (number divisibleByInt 3)) |+|    ("Buzz" when (number divisibleByInt 5)) getOrElse    number.show

Тут type class Show дает типу T возможность превращения в строку, |+| синтаксис моноида для сложения и getOrElse задает значение по-умолчанию. Все в общем виде и для любых типов, мы могли бы и от строк "Fizz" & "Buzz" абстрагироваться, но это лишнее на мой взгляд.

Конец

Все, что нам осталось сделать это (1 to 100) map fizzBuzz[Int] и куда-нибудь вывести результат. Но это уже совсем другая история...

Подробнее..

Категории: Программирование , Scala , Функциональное программирование , Functional programming , Fizzbuzz , Fun

Перевод Решение Fizzbuzz при помощи теоремы Эйлера

22.03.2021 10:20:41 |

Автор: admin

FizzBuzz это известная задачка на программирование, которую обычно дают в технической части собеседований. Она формулируется примерно так:

Напишите функцию, выводящую список целых чисел от 1 до 100, но вместо каждого числа, кратного 3, она должна выводить Fizz, а вместо каждого числа, кратного 5, выводить Buzz. Вместо чисел, кратных и 3, 5, программа должна выводить FizzBuzz; все остальные числа должны выводиться без изменений.

Можно написать функцию, вообще не использующую условную логику и вместо этого разделяющую целые числа на 4 возможные категории (обычное решение оставим в качестве упражнения заинтересованному читателю):

Имеющие делитель 3, но не 5
Имеющие делитель 5, но не 3
Имеющие делитель и 3, и 5
Не имеющие делитель 3 и 5

Нам нужна функция, которая будет возвращать:

Fizz, если $n \equiv 0 \pmod 3$ и $inline$ является взаимно простым с 5
Buzz, если $n \equiv 0 \pmod 5$ и $inline$ является взаимно простым с 3
FizzBuzz, если $n \equiv 0 \pmod 3$ и $n \equiv 0 \pmod 5$
$inline$ во всех остальных случаях.

Рассмотрим реализацию такой функции на Python:

[(lambda n: { 1: n, 6: "Fizz", 10: "Buzz", 0: "FizzBuzz" }[n**4%15])(n+1) for n in range(100)]

Та же функция на Ruby:

(1..100).map{|n| {1 => n, 6 => "Fizz", 10 => "Buzz", 0 => "FizzBuzz"}[n**4%15] }

Как мы и ожидали, каждая из этих функций возвращает список целых чисел от 1 до 100 с подставленными в нужные места Fizz, Buzz и FizzBuzz.

Но почему? Откуда взялись постоянные значения 0, 6, 10 и 1? Почему $n^4 \mod 15$ возвращает 6 для чисел, кратных 3, но не 5, 10 для чисел, кратных 5, но не 3, 0 для чисел, кратных 5 и 3 и 1 во всех остальных случаях? И самое важное справедливо ли это для любого $inline$ , которое мы выберем?

I. n^4 mod 15 решает FizzBuzz

Доказательство таково:

$n^4 \mod {15} = \begin{cases} 0, & \text{if $n$ is divisible by 3 and 5} \newline 6, & \text{if $n$ is divisible by 3 and coprime to 5} \newline 10, & \text{if $n$ is divisible by 5 and coprime to 3} \newline 1, & \text{if $n$ is coprime to 3 and 5} \end{cases}$

Первый случай тривиален; если n делится и на 3, и на 5, то после возведения n в любую степень возвращаемый $\mod 15$ результат всегда будет равен 0, та как любое целое число с делителями 3 и 5 будет также кратным 15 $inline$ .

Во втором случае у нас есть 3 как делитель некой константы c:

$3c^4 \equiv 6 \pmod{15}$

или

$3c^4 \mod 15 = 6$

для каждой константы c > 0, если c является взаимно простым с 5. (Если c не является взаимно простым с 5, то у нас возник первый случай, который вернёт 0.)

Для начала предположим, что $inline$ . Это даёт $3^4 \mod 15$ или $81 \mod 15$ , что вернёт 6: $inline$ , с остатком 6 от 81.

Предположим, что c является целым > 1. Применим степень к каждому множителю и воспользуемся равенством $inline$ :

$\begin{aligned} 3^4c^4 & \mod 15 \newline 81c^4 & \mod 15 \newline (81 + 81(c^4 - 1)) & \mod 15 \end{aligned}$

Давайте рассмотрим отдельно выражение $inline$ . Из теоремы Эйлера в теории чисел мы знаем, что поскольку $inline$ является взаимно простым с 5, то $c^4 \mod 5$ равно 1; если $inline$ имеет остаток 1, то это должен быть случай, когда $inline$ ровно делится на 5; то есть, вне зависимости от значения $inline$ , если оно является взаимно простым с 5, то $inline$ имеет делитель 5. Другой делитель не важен, поэтому давайте перепишем $inline$ как $inline$ .

Теорема Эйлера в теории чисел

Теорема Эйлера заключается в том, что $a^{(n)} \equiv 1 (\mod n)$ , где $inline$ является взаимно простым с $inline$ , а $inline$ это пси-функция Эйлера; пси-функция $inline$ возвращает количество целых чисел меньше $inline$ , являющихся взаимно простыми с $inline$ . Для каждого простого числа $inline$ , $inline$ равна $inline$ .

Леонард Эйлер

$\begin{align} (81 + 81(5x)) &\mod 15 \newline (81 \mod 15 + 81(5x) \mod 15) &\mod 15 \newline (6 + 81(5x) \mod 15) &\mod 15 \newline 6 \mod 15 \end{align}$

Мы можем переписать это во вторую строку благодаря следующему свойству модулярных выражений: $(a + b) \mod n = (a \mod n + b \mod n) \mod n$ . В третьей строке выражение $inline$ имеет делители и 3, и 5, поэтому $81(5x) \mod 15 = 0$ , что даёт нам $6 \mod 15$ , то есть 6.

То есть для любого $inline$ , являющегося взаимно простым с 5 и > 1, выражение $3c^4 \mod 15$ вернёт 6.

Благодаря тому же процессу мы выясним, что $5c^4 \mod 15$ всегда возвращает 10; при $inline$ мы имеем $625 \mod 15$ , что равно 10. Для $inline$ (взаимно простое с 3) мы можем записать

$(625 + 625(c^4 - 1)) \mod 15$

Теорема Эйлера говорит нам, что если $inline$ является взаимно простым с 3, то $c^2 \equiv 1 \mod 3$ ; но у нас есть $inline$ . Однако $inline$ это $inline$ , а поскольку $ab \mod n = ((a \mod n)( b \mod n)) \mod n$ , то $c^4 \mod 3$ также равно 1.

Опять же, если $c^4 \equiv 1 (\mod 3)$ , то $inline$ нацело делится на 3 и имеет делитель 3. Это снова сокращает второй член до 0, оставляя $625 \mod 15$ , что снова равно 10.

У нас остаётся случай, в котором есть некое число $inline$ , являющееся взаимно простым с 3 и 5. Если $inline$ равно 1, то получаем $1 \mod 15$ , то есть 1.

Если $inline$ > 1, мы снова можем записать это как $(1 + (c^4 - 1)) \mod 15$ . Так как мы знаем, что если $inline$ является взаимно простым с 3 и 5, $c^4 \equiv 1 (\mod 3)$ и $c^4 \equiv 1 (\mod 5)$ , то $inline$ имеет делители 3 и 5.

Поэтому снова:

$\begin{aligned} (1 + (c^4 - 1)) &\mod 15 \newline (1 \mod 15 + (c^4 - 1) \mod 15) &\mod 15 \newline (1 + 0) &\mod 15 \newline 1 &\mod 15 \newline 1 \end{aligned}$

То есть $n^4 \mod 15$ всегда будет возвращать 0, если и 3, и 5 являются делителями $inline$ , возвращать 6, если делителем является 3, но не 5, возвращать 10, если делителем является 5, но не 3, и 1, если $inline$ является взаимно простым и с 3, и с 5, а функция вида

->(n){ {1 => n, 6 => "Fizz", 10 =>
"Buzz", 0 => "FizzBuzz"}[n**4%15] }

всегда будет возвращать правильный результат FizzBuzz для каждого $inline$ (до того, как $inline$ не переполнит тип integer, используемый в компьютере).

II. Решение любой задачи категории FizzBuzz

Схожую функцию можно создать для любой похожей задачи, которые я буду называть задачами категории FizzBuzz. (Задачи категории FizzBuzz: например, выводить Foo вместо чисел, кратных 2, Bar вместо чисел, кратных трём, Baz вместо чисел, кратных 5 и выполнить конкатенацию каждого слова для чисел, имеющих больше одного из делителей 2,3 и 5). Выбираемые в качестве делителей числа не обязаны быть простыми, но если одно из них имеет в качестве делителя другое, то некоторые группы не существуют. Например, если мы решили изменить FizzBuzz так, чтобы кратные 2 возвращали Fizz, а кратные 4 возвращали Buzz (вместо традиционных 3 и 5), то увидим Fizz для каждого кратного 2, FizzBuzz для кратного 2 и 4, но никогда не увидим Buzz, потому что не существует числа, кратного 4, являющегося взаимно простым с 2.

Представленное ниже обобщённое решение не такое уж и общее, как я сказал: существует множество пар чисел, для которого оно не сработает; поэтому делители нужно выбирать гораздо тщательнее. Оно сработает для уникальных простых чисел, но не всегда хорошо для составных чисел. Хочу поблагодарить автора этого очень подробного поста, объясняющего подробности того, почему общая формула не будет работать для составных чисел.

Написанное выше уравнение для решения FizzBuzz можно также записать в виде

$n^{LCM((3),(5))} \mod (3 \cdot 5)$

где $inline$ это пси-функция Эйлера, а $inline$ наименьшее общее кратное.

В общем виде для любого множества из $inline$ делителей $inline$ , для которого нам нужна функция типа FizzBuzz, можно использовать формулу:

$n^{LCM((n_1),(n_2),..(n_k))} \mod \prod_{i=1}^k n_i$

Для функции типа FizzBuzz, возвращающей Foo вместо чисел, кратных 7, и Bar вместо чисел, кратных 11, найдём:

$n^{LCM((7),(11))} \mod (7 \cdot 11)$

$inline$ равно 6, а $inline$ равно 10, и $inline$ (наименьшее общее кратное) для 6 и 10 равно 30. То есть уравнение примет вид:

$n^{30} \mod 77$

Реализация на Python:

[(lambda n: { 1: n, 7**30%77: "Foo", 11**30%77: "Bar", 0: "FooBar" }[n**30%77])(n+1) for n in range(100)]

Это даст нам ожидаемый результат:

[1, 2, 3, 4, 5, 6, 'Foo', 8, 9, 10, 'Bar', 12, 13, 'Foo', 15, 16, 17, 18, 19, 20, 'Foo', 'Bar', 23, 24, 25, 26, 27, 'Foo', 29, 30, 31, 32, 'Bar', 34, 'Foo', 36, 37, 38, 39, 40, 41, 'Foo', 43, 'Bar', 45, 46, 47, 48, 'Foo', 50, 51, 52, 53, 54, 'Bar', 'Foo', 57, 58, 59, 60, 61, 62, 'Foo', 64, 65, 'Bar', 67, 68, 69, 'Foo', 71, 72, 73, 74, 75, 76, 'FooBar', 78, 79, 80, 81, 82, 83, 'Foo', 85, 86, 87, 'Bar', 89, 90, 'Foo', 92, 93, 94, 95, 96, 97, 'Foo', 'Bar', 100]

Вывод

Итак,

$$display$$a^{LCM((n_1),(n_2),..(n_k))} \equiv \begin{cases} 0\pmod {\prod_{i=1}^k n_i}, & \text{if $n$ is divisible by every $n_1,n_2,..n_k$} \newline r_1,r_2,..r_k\pmod {\prod_{i=1}^k n_i}, & \text{a distinct result for every other combination of factors in $n_1,n_2,..n_k$} \newline 1\pmod {\prod_{i=1}^k n_i}, & \text{if $n$ is coprime to every $n_1,n_2,..n_k$} \end{cases}$$display$$

если числа $inline$ являются уникальными простыми числами. Снова благодарю автора этого поста за столь наглядную иллюстрацию этого.

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

Подробнее..

Категории: Программирование , Fizzbuzz , Алгоритмы , Математика , Эйлер , Модулярная функция

	Русский
	English

Fizzbuzz

FizzBuzz по-сениорски

Functional FizzBuzz на Scala

Задача

Решение

Начнем с делимости

FizzBuzz

Конец

Перевод Решение Fizzbuzz при помощи теоремы Эйлера

I. n^4 mod 15 решает FizzBuzz

II. Решение любой задачи категории FizzBuzz

Вывод

Категории

Последние комментарии