как получить случайное число до 1 млн

[HelenSecuriter]

Компиллятор Visual Studio 2008, но это вроде роли не играет..
Мне вообще требуются такие большие числа для испытания скорости работы алгоритма, причем чтобы не нужно было вводить с клавиатуры. И еще вопрос: посмотрите, кто разбирается, правильно ли у меня функция вычисляет чило знаков в десятичной записи числа Эн факториал:

long nfigfact(long N){
	double res=N*log10(N/M_E)+1;
	return res-floor(res)<0.5?(long)floor(res):(long)ceil(res);//эта строка округляет к ближайшему целому
}

[Dogmat]

Число знаков - всмысле сколько цифр? Я правильно понимаю?

Ну, вот:

#include <math>
#include <iostream>

using namespace std;

unsigned __int64 nodl(unsigned __int64 n)
{
    unsigned __int64 res(0);

    if (n < 2)
        res = 1;
    else
         res = n * nodl(n - 1);

    return res;
}

long roundl(long double d)
{
    long div = (d < 0) ? -d : d;
    long double mod = (d < 0) ? (-d - div) : (d - div);

    if (mod > 0.5)
        ++div;

    return (d < 0) ? -div : div;
}

int main(int argc, char* argv[])
{
    for (int i = 1; i < 21; ++i)
    {
        unsigned __int64 nod = nodl(i);

        long double res = i * log10(i / M_E) + 1;

        cout << i << " " << nod << " " << floorl(res)
                                << " " << roundl(res)
                                << " " << ceill(res)
                                << endl;
    }

    cin.get();
}

Прогнал на 20 значениях, дальше переполнение. Можно использовать double, но уже сейчас видно, что незачем. Похоже, что неверная формула, никакое округление не помогло. По поводу формулы к сожалению ничего сказать не могу...

[HelenSecuriter]

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

unsigned __int64 nodl(unsigned __int64 n)
{
unsigned __int64 res(0);

if (n < 2)
res = 1;
else
res = n * nodl(n - 1);

return res;
}

Зачем нужна эта функция, к тому же она вроде рекурсивная?

[Dogmat]

блин ) назвал неправильно ) Факториал она считает, а назвал НОД, прошу прощения. Да - рекурсивная, для проверки сгодится и рекурсия. При больших n, конечно выскочит stackoverflow, но я лично не видел, чтобы брали большие факториалы. Можно и цикл.
Использовал просто для проверки, считал факториал, выводил на консоль. Потом считал по вашей формуле количество знаков, округлял до большего, до меньшего и до ближайшего. Сравнивал. Ну и похоже чего-то не хватает в формуле. Проверял на факториалах до 20!. Для __int64 дальше будет переполнение, но уже на 20 значениях видно расхождение. Что касается 1000000! (ого), а как вы его считали? Сдается мне. что даже при использовании long double произойдет переполнение. А calc у меня при вычислении 1000000! выдал freezy. Так что, если вам удастся посчитать факториал 1000000! там наверняка больше 2 млн. знаков и будет, потому что при использовании long double для 1000! знаков у меня было больше 2500.

Почему-то молчат математики...

[Dogmat]

А можно узнать откуда формула взята? Или на основании чего получена...

[HelenSecuriter]

формула взята из довольно авторитетного источника: Р. Седжвик. Фундаментальные алгоритмы на С++/*Есть такие же на С и Java, но я Java не знаю, а на С не интересно*/. Часть 1-4. Там также есть и доказательство, но оно смутное и я не поняла, для двоичной системы
В том-то и дело, ято явное вычисление факториала не получится, нужно косвенно.
И если функция неправильно считает, тогда где ошибка?

[Dogmat]

Ну, общем, достала эта формула уже ) Я пришел к выводу, что все верно, не понял только, как появилась единица. Корнень за единицу приняли? Я так полагаю, что ответ и должен быть приблизительным, поскольку вычисления с логарифмами приблизительны. А так, опираясь на:
1) lg(n) приблизительно равно количеству цифр требуемых для представления числа;
2) Формула Стирлинга.
Ну и получаем lg(n!) приблизительно равно количеству разрядов, необходимых для представления числа n! в системе счисления в основании логарифма (у нас 10). А по Стирлингу n! = ((n/e)^n) * sqrt(2 * pi * n) * (1 + O); Все как у вас, если вы корень за 1 приняли. Я корень оставил и получил близкие результаты.

        const long double pi = 3.1415926535897932384626433832795;
        long double sqrt = sqrtl(2 * pi * n);
        long double O = (1 + 1 / (12 * n) + 1 / (288 * n * n)); // + ...
        long double res = n * log10l(n / M_E) + log10l(sqrt * O);

Потом я решил проверить результаты для двоичной системы счисления. И получил аналогичные, в смысле точности, результаты.

        const long double pi = 3.1415926535897932384626433832795;
        long double sqrt = sqrtl(2 * pi * n);
        long double O = (1 + 1 / (12 * n) + 1 / (288 * n * n)); // + ...
        long double res = (n * logl(n / M_E) + logl(sqrt * O)) / logl(2);

Такая форма записи будет универсальная для любой системы счисления, достаточно поменять параметр у последнего logl с 2 на base.


Затем решил проверить уж совсем наверняка простую формулу, lg(n) (по основанию 2).

int main(int argc, char* argv[])
{
    for (int n = 1; n < 1025; ++n)
    {
        long double res = logl(n) / logl(2);

        cout << n << " " << floorl(res) << " " << roundl(res) << " " << ceill(res) << endl;
    }

    cin.get();
}

Получается для dec-системы счисления неверно считает только для 1!.
Для bin-системы неверное считает для 1! и 2!.
А дальше все стабильно, при условии, что результат округляем в сторону большего в любом случае (как и пишет Седжвик - наименьшее целое, больше lg(n!)).

Вот переправленный пример для dec (base == 10), с использованиеим long double, для первых 1000!.

#include <math>
#include <iostream>

using namespace std;

long double factl(unsigned long n)
{
    long double res(1);

    for (unsigned long i = 1; i <= n; ++i)
        res *= i;

    return res;
}

long double roundl(long double d)
{
    long div = (d < 0) ? -d : d;
    long double mod = (d < 0) ? (-d - div) : (d - div);

    if (mod > 0.5)
        ++div;

    return (d < 0) ? -div : div;
}

int main(int argc, char* argv[])
{
    for (int n = 1; n < 1000; ++n)
    {
        long double fact = factl(n);

        unsigned int base(10);
        const long double pi = 3.1415926535897932384626433832795;
        long double sqrt = sqrtl(2 * pi * n);
        long double O = (1 + 1 / (12 * n) + 1 / (288 * n * n)); // + ...
        long double res = (n * logl(n / M_E) + logl(sqrt * O)) / logl(base);

        cout << n << "   " << fact << "    " << floorl(res)
                                   << "    " << roundl(res)
                                   << "    " << ceill(res)
                                   << endl;
    }

    cin.get();
}

Смотрим второй и последний столбики - значение факториала и res округленный до большего. В прикрепленном файле результат вычислений для первых 20 значений в dec и bin.

[VintProg]

(rand()*rand())%(value+1)

[БалаШагаЛ]

До 1 млн.:

long long s;
int a=rand()%1000;
s=1000*a;
s+=rand()%1000+1;