Так для домашнего проекта нет ничего проще, чем воспользоваться стандартным классом длинных целых.
Что касается произведения, то я работаю в Java, где нужно использовать int и long. Но, вне зависимости от языка, суть в том, что нужно всегда помнить о возможности переполнения. Использовать правильное сочетание 32-битового и 64-битового типов - да, один из способов. (Если, конечно, оба беззнаковые либо оба знаковые.) При этом, правда, придется привести произведение к нужному более краткому типу. Но уже, например, для трехмерной матрицы этот способ не подойдет. Не подойдет и для изображения в формате RGBRGB... - там добавляется умножение на число каналов.
Наиболее простой и универсальный способ контроля - деление максимального допустимого размера на один из сомножителей. Правда, это медленно, но при отведении памяти это несущественно. Если нужна скорость (умножать надо не только для отведения памяти, но и, скажем, при вычислении индекса), то можно использовать прием из Hackers Delight. В последних версиях Java соответствующии функции добавлены в библиотеку Math: обычные арифметические операции, но гарантирующие исключение в случае переполнения.
Что действительно может понадобиться в реальной жизни, так это проверка переполнения при самых обыкновенных вычислениях - сумм, разностей, произведений. Вот, например, предложите задачу: написать функцию с целыми параметрами dimX, dimY, которая создает матрицу dimX x dimY в простом линейном массиве (не двумерном, даже если язык позволяет) и заполняет ее чем-нибудь полезным, ну хотя бы рисует там круг из единичек. И вот, тест на квалификацию: догадается ли кандидат перед отведением памяти проверить, что произведение dimX * dimY вычисляется без переполнения, и в противном случае выдать соответствующее исключение "слишком большой массив". Сколько я видел кода, который не задумывается о таких "мелочах жизни" - и, соответственно, при неудачных dimX и dimY ведет себе неадекватно (вплоть до порчи памяти в языках типа C++). Я уже не говорю о более тонких мометах, вроде того, что для знаковых x и y неравенство x - y < 0 вовсе обязательно означает, что x < y...
Задача, конечно, интересная... для олимпиады по информатике не слишком высокого ранга. Но при чем тут собеседование? Хороший сотрудник должен владеть существующими инструментами, например, разбираться в типичных алгоритмах и уметь их реализовывать. Вероятность столкнуться с подобной задачей в реальной практике, по моему опыту, весьма невелика, причем даже за десятки лет интенсивной работы в области алгоритмов. А если даже и возникнет подобная нестандартная ситуация (бывает всякое), то гораздо полезнее сотрудник, который сможет быстро найти готовое решение в интернете, в книгах (вроде Hackers Delight) или на форумах, чем тот, кто решит подобную задачу сам. Ибо почти наверняка готовое решение окажется профессиональнее и эффективнее.
Если же говорить о конкретно этой задаче, то, во-первых, надо отмести как неправдоподобное требование неизменяемости массива. Это может быть важным либо 1) при необходимости разработки очень фундаментальной стандартной библиотеки, которой будут пользоваться миллионы, например, базового API языка; 2) если размер массива сопоставим с объемом оперативной памяти, т.е. мы не можем позволить себе создать его копию. Первое, однако, явно мимо кассы - в этом случае над задачей будет работать команда профессиональных инженеров, а никак не новичок. Второе же, да, бывает, но очень маловероятно, что задача будет настолько простой. Большие массивы - это обычно изображения, карты, базы данных, а никак не наборы индексов. А самое главное, что в этом случае быстродействие O(N) становится важнее, чем неизменяемость - уж лучше сбросить исходный массив во внешнюю память, чтобы можно было изменять. Кстати, даже в первом случае нормальное решение, как минимум, должно проверить наличие свободной памяти и предпочесть копирование массива в случае, если памяти достаточно и если это повышает быстродействие.
Во-вторых, из реальных подходов к решению я бы выбрал либо сортировку, либо таблицу. В реальной ситуации там вряд ли будут такие удобные числа, как 1..N, но если это и правда целые числа и если их диапазон не слишком велик, то таблица, скорее всего, окажется оптимальным решением.
А вот если это не целые числа, а, к примеру, вещественные, то я бы очень оценил кандидата, который не "поведется" на стандартные библиотечные хеш-таблицы и предложит сортировку! Точнее, настоит на том, чтобы сравнить производительность обоих вариантов. Да, формально хеш-таблицы быстрее, но в реальности - при тех объемах, которые реально могут поместиться в ОЗУ - весьма вероятно, что N log N тщательно "вылизанной" библиотечной сортировки с легкостью обгонят поддержку структуру данных универсального хэша. Особенно если это язык вроде Java, где HashMap работает с объектами, размещаемыми в куче. Очень хорошо, если соискатель задумается о кэше процессора, о том, как именно будет происходить обращение к памяти - вразброс или последовательно, о том, поддается ли решение распараллеливанию на многоядерных процессорах и будет ли реальный прок от такого распараллеливания...
Вот эти соображения, да, важны для профессионального сотрудника, они кое-что говорят о его опыте работы и умении создавать эффективные решения. А поиск супер-изящных алгоритмов при искусственных ограничениях, по-моему, лучше оставить олимпиадникам. Вроде тех, кто в свое время пользовались нестандартным форматом Intel-команды AAD, чтобы сэкономить лишний байт памяти, умножая число на множитель, отличный от 10 :)
Так для домашнего проекта нет ничего проще, чем воспользоваться стандартным классом длинных целых.
Что касается произведения, то я работаю в Java, где нужно использовать int и long. Но, вне зависимости от языка, суть в том, что нужно всегда помнить о возможности переполнения. Использовать правильное сочетание 32-битового и 64-битового типов - да, один из способов. (Если, конечно, оба беззнаковые либо оба знаковые.) При этом, правда, придется привести произведение к нужному более краткому типу. Но уже, например, для трехмерной матрицы этот способ не подойдет. Не подойдет и для изображения в формате RGBRGB... - там добавляется умножение на число каналов.
Наиболее простой и универсальный способ контроля - деление максимального допустимого размера на один из сомножителей. Правда, это медленно, но при отведении памяти это несущественно. Если нужна скорость (умножать надо не только для отведения памяти, но и, скажем, при вычислении индекса), то можно использовать прием из Hackers Delight. В последних версиях Java соответствующии функции добавлены в библиотеку Math: обычные арифметические операции, но гарантирующие исключение в случае переполнения.
А... зачем может пригодиться такой факториал? :)
Что действительно может понадобиться в реальной жизни, так это проверка переполнения при самых обыкновенных вычислениях - сумм, разностей, произведений. Вот, например, предложите задачу: написать функцию с целыми параметрами dimX, dimY, которая создает матрицу dimX x dimY в простом линейном массиве (не двумерном, даже если язык позволяет) и заполняет ее чем-нибудь полезным, ну хотя бы рисует там круг из единичек. И вот, тест на квалификацию: догадается ли кандидат перед отведением памяти проверить, что произведение dimX * dimY вычисляется без переполнения, и в противном случае выдать соответствующее исключение "слишком большой массив". Сколько я видел кода, который не задумывается о таких "мелочах жизни" - и, соответственно, при неудачных dimX и dimY ведет себе неадекватно (вплоть до порчи памяти в языках типа C++). Я уже не говорю о более тонких мометах, вроде того, что для знаковых x и y неравенство x - y < 0 вовсе обязательно означает, что x < y...
Задача, конечно, интересная... для олимпиады по информатике не слишком высокого ранга. Но при чем тут собеседование? Хороший сотрудник должен владеть существующими инструментами, например, разбираться в типичных алгоритмах и уметь их реализовывать. Вероятность столкнуться с подобной задачей в реальной практике, по моему опыту, весьма невелика, причем даже за десятки лет интенсивной работы в области алгоритмов. А если даже и возникнет подобная нестандартная ситуация (бывает всякое), то гораздо полезнее сотрудник, который сможет быстро найти готовое решение в интернете, в книгах (вроде Hackers Delight) или на форумах, чем тот, кто решит подобную задачу сам. Ибо почти наверняка готовое решение окажется профессиональнее и эффективнее.
Если же говорить о конкретно этой задаче, то, во-первых, надо отмести как неправдоподобное требование неизменяемости массива. Это может быть важным либо 1) при необходимости разработки очень фундаментальной стандартной библиотеки, которой будут пользоваться миллионы, например, базового API языка; 2) если размер массива сопоставим с объемом оперативной памяти, т.е. мы не можем позволить себе создать его копию. Первое, однако, явно мимо кассы - в этом случае над задачей будет работать команда профессиональных инженеров, а никак не новичок. Второе же, да, бывает, но очень маловероятно, что задача будет настолько простой. Большие массивы - это обычно изображения, карты, базы данных, а никак не наборы индексов. А самое главное, что в этом случае быстродействие O(N) становится важнее, чем неизменяемость - уж лучше сбросить исходный массив во внешнюю память, чтобы можно было изменять. Кстати, даже в первом случае нормальное решение, как минимум, должно проверить наличие свободной памяти и предпочесть копирование массива в случае, если памяти достаточно и если это повышает быстродействие.
Во-вторых, из реальных подходов к решению я бы выбрал либо сортировку, либо таблицу. В реальной ситуации там вряд ли будут такие удобные числа, как 1..N, но если это и правда целые числа и если их диапазон не слишком велик, то таблица, скорее всего, окажется оптимальным решением.
А вот если это не целые числа, а, к примеру, вещественные, то я бы очень оценил кандидата, который не "поведется" на стандартные библиотечные хеш-таблицы и предложит сортировку! Точнее, настоит на том, чтобы сравнить производительность обоих вариантов. Да, формально хеш-таблицы быстрее, но в реальности - при тех объемах, которые реально могут поместиться в ОЗУ - весьма вероятно, что N log N тщательно "вылизанной" библиотечной сортировки с легкостью обгонят поддержку структуру данных универсального хэша. Особенно если это язык вроде Java, где HashMap работает с объектами, размещаемыми в куче. Очень хорошо, если соискатель задумается о кэше процессора, о том, как именно будет происходить обращение к памяти - вразброс или последовательно, о том, поддается ли решение распараллеливанию на многоядерных процессорах и будет ли реальный прок от такого распараллеливания...
Вот эти соображения, да, важны для профессионального сотрудника, они кое-что говорят о его опыте работы и умении создавать эффективные решения. А поиск супер-изящных алгоритмов при искусственных ограничениях, по-моему, лучше оставить олимпиадникам. Вроде тех, кто в свое время пользовались нестандартным форматом Intel-команды AAD, чтобы сэкономить лишний байт памяти, умножая число на множитель, отличный от 10 :)