VPF::Длина чисел - Форум программистов

demon071

Дата 12.5.2007, 09:50 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 13
Регистрация: 25.11.2006

Репутация: нет
Всего: 1

Подскажите пожалуйста решение следующей проблемы:
При вводе целого числа типа int, должна выводиться длина этого числа.
Объясните что нужно сделать.

Voldemar2004

Дата 12.5.2007, 10:18 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1650
Регистрация: 25.12.2004

Репутация: нет
Всего: 23

О, господи, этот вопрос обсуждался буквально неделю назад в одном из соседних топиков:

Код

/* функция вычисления количества цифр в целом числе */
int Num_Count(int a)
{
int f;
f=0;

        do
        {a/=10; f++;}
        while(a);

return f;
}

Добавлено @ 10:32
Или так:

Код

#include <iostream.h>

int LenInt(char* Value);

int main(int argc, char* argv[])
{

cout << LenInt("5346756745675675477567567455747575675457650");

return 0;
}

int LenInt(char* Value){
return strlen(Value);
}

Это сообщение отредактировал(а) Voldemar2004 - 12.5.2007, 10:35

--------------------

i_i
(';')
(V)

user posted image

Anikmar

Дата 12.5.2007, 10:35 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

Репутация: 9
Всего: 59

А второй пример что делает?! smile

Где там вообще хоть один int?!

Voldemar2004

Дата 12.5.2007, 10:37 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1650
Регистрация: 25.12.2004

Репутация: нет
Всего: 23

Ну пусть аргументом функции будет char* smile

Добавлено через 1 минуту и 32 секунды
Я подумал, что во 2-ом примере, пользователь будет вводить только числа типа int.

Это сообщение отредактировал(а) Voldemar2004 - 12.5.2007, 10:37

--------------------

i_i
(';')
(V)

user posted image

Anikmar

Дата 12.5.2007, 10:47 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

Репутация: 9
Всего: 59

Цитата(Voldemar2004 @ 12.5.2007, 10:37

)

Ну пусть аргументом функции будет char*

Добавлено через 1 минуту и 32 секунды
Я подумал, что во 2-ом примере, пользователь будет вводить только числа типа int.

Так вы только запутаете человека. Длина строки символов ни какого отношения к длине числа int не имеет.

W4FhLF

Дата 12.5.2007, 10:48 (ссылка)

(нет голосов)

Загрузка ...

found myself

Профиль
Группа: Участник Клуба
Сообщений: 2831
Регистрация: 2.12.2006

Репутация: 20
Всего: 121

Код


int LenOfInt(int num)
{
    int r = 0;
    __asm {
        FLDLG2
        FILD DWORD PTR[num]
        FYL2X
        FIST DWORD PTR[r]
    }; 
    return ++r;
}

Оптимизированный вариант.

--------------------

"Бог умер" © Ницше
"Ницше умер" © Бог

Anikmar

Дата 12.5.2007, 10:52 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

Репутация: 9
Всего: 59

Цитата(W4FhLF @ 12.5.2007, 10:48

)

код C++
int LenOfInt(int num)
{
    int r = 0;
    __asm {
        FLDLG2
        FILD DWORD PTR[num]
        FYL2X
        FIST DWORD PTR[r]
    };
    return ++r;
}
Оптимизированный вариант.

Да...
Это точно пример для обучения smile

W4FhLF

Дата 12.5.2007, 10:54 (ссылка)

(нет голосов)

Загрузка ...

found myself

Профиль
Группа: Участник Клуба
Сообщений: 2831
Регистрация: 2.12.2006

Репутация: 20
Всего: 121

Anikmar, ну не автору, так кому-нибудь ещё пригодится, да и потом я могу объяснить, если кому-то это понадобится smile

--------------------

"Бог умер" © Ницше
"Ницше умер" © Бог

Voldemar2004

Дата 12.5.2007, 10:55 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1650
Регистрация: 25.12.2004

Репутация: нет
Всего: 23

Цитата(Anikmar @ 12.5.2007, 11:47

)

Так вы только запутаете человека. Длина строки символов ни какого отношения к длине числа int не имеет.

Так надо узнать, сколько занимает это число в памяти

Код

sizeof()

или количество цифр в числе ?

Добавлено через 1 минуту и 8 секунд

Цитата(W4FhLF @ 12.5.2007, 11:54

)

если кому-то это понадобится

W4FhLF, мне интересно, объясни. smile

--------------------

i_i
(';')
(V)

user posted image

W4FhLF

Дата 12.5.2007, 11:06 (ссылка)

(нет голосов)

Загрузка ...

found myself

Профиль
Группа: Участник Клуба
Сообщений: 2831
Регистрация: 2.12.2006

Репутация: 20
Всего: 121

Цитата(Voldemar2004 @ 12.5.2007, 10:55

)

W4FhLF, мне интересно, объясни.

ok

кол-во цифр в числе есть log10(|x|)+1

Код


{ загрузка в регистр сопроцессора ST(0) значения десятичного логарифма числа 2 (log10(2)) }
FLDLG2                             
{ загрузка целочисленного значения в регистр сопроцессора ST(1) }
FILD DWORD PTR[num]
{ вычисление выражения по формуле y*log2(x). 
x - ST(0)
y - ST(1)
Результат в ST(0) }
FYL2X                                
{ на данном этапе в регистре ST(0) значение log10(num) }
{ сохранение числа из ST(0) в целочисленной форме в переменную r}
FIST DWORD PTR[r]

--------------------

"Бог умер" © Ницше
"Ницше умер" © Бог

vinter

Дата 12.5.2007, 11:24 (ссылка)

(нет голосов)

Загрузка ...

Explorer

Профиль
Группа: Завсегдатай
Сообщений: 2735
Регистрация: 1.4.2006
Где: Н.Новгород

Репутация: 13
Всего: 56

Код


size_t Num_Count(int a)
{
  char szDigit[256];
  sprintf(szDigit, "%d", a);
  if(a >= 0)
    return strlen(szDigit);
  else
     return (strlen(szDigit) - 1);

}

Добавлено @ 11:24
W4FhLF, мощно завернул smile

Это сообщение отредактировал(а) vinter - 12.5.2007, 11:25

--------------------

Мой блог

jonie

Дата 12.5.2007, 13:15 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 5613
Регистрация: 21.8.2005
Где: Владимир

Репутация: 15
Всего: 118

W4FhLF а модуль-то не надо в код ввести разве (формула-то одно, код чуток иное)? LenOfInt(-x) даст интересный результат...иль отрицательный числа = нечисла? а такто мысля однозначно правильная.. ну разве что только аппаратная зависимость появилась...

Это сообщение отредактировал(а) jonie - 12.5.2007, 13:16

--------------------

Что-то не поняли? -> Напейтесь до зеленых человечков... эта сверхцивилизация Вам поможет...

W4FhLF

Дата 12.5.2007, 13:34 (ссылка)

(нет голосов)

Загрузка ...

found myself

Профиль
Группа: Участник Клуба
Сообщений: 2831
Регистрация: 2.12.2006

Репутация: 20
Всего: 121

jonie, special for you:

Код


int LenOfInt(int num)
{
    int r = 0;
    __asm {
        CMP DWORD PTR[num],0
        JNS pstv
        NEG num
        pstv:
        FLDLG2
        FILD DWORD PTR[num]
        FYL2X
        FIST DWORD PTR[r]
    }; 
    return ++r;
}

Enjoy!

--------------------

betal

Дата 12.5.2007, 15:51 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 208
Регистрация: 26.12.2006

Репутация: нет
Всего: 1

Цитата(Anikmar @ 12.5.2007, 10:52

)

Это точно пример для обучения smile

в яблочко. Зачет smile

Добавлено через 11 минут и 47 секунд

Цитата(W4FhLF @ 12.5.2007, 10:54

)

Anikmar, ну не автору, так кому-нибудь ещё пригодится, да и потом я могу объяснить, если кому-то это понадобитсяsmile

Не все павильно. Оптимизированый код исче никому не помешал. Спасибо...

--------------------

101100010100001101100001110100101111011легкие деньги

Ln78

Дата 13.5.2007, 16:13 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 274
Регистрация: 25.11.2006

Репутация: 13
Всего: 15

W4FhLF, я с благоговением отношусь к ассемблерным вставкам, если только мне лично не нужно сопровождать такой код, тем более – искать в нём ошибки. Но в данном случае, учитывая, что в основу положена формула log10(|x|)+1, т.е. вычисление трансцендентной функции вместо операции с целыми числами, я усомнился в великой оптимизации: если я лично напишу код на ассемблере, а не предоставлю это компилятору, неужели только за счёт этого будет выигрыш в скорости? Решив проверить, написал 5 вариантов. Эти варианты относятся к положительным (начиная с 1) 4-байтным целым числам.

Код


int LenOfInt1(int num)
{
   int r = 0;
   __asm {
      FLDLG2
      FILD DWORD PTR[num]
      FYL2X
      FIST DWORD PTR[r]
   }; 
   return ++r;
}

int LenOfInt2(int num)
{
   return int( log10( double( num ) ) )+ 1;
}

int LenOfInt3(int num)
{
   int N = 0;
   do 
   {
      num /= 10;
      N++;
   } while( num );
   return N;
}

int LenOfInt4(int num)
{
   int arN[] = {10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
   int n = 0;
   while ( num >= arN[n] && n < 8 ) n++;
   return n + 1;
}

int LenOfInt5(int n)
{
   if( n < 1000000 )
   {
      if( n < 1000 )
      {
         if( n < 10 ) return 1;
         if( n < 100 ) return 2;
         return 3;
      } else {
         if( n < 10000 ) return 4;
         if( n < 100000 ) return 5;
         return 6;
      }
   } else {
      if ( n < 10000000 ) return 7;
      if ( n < 100000000 ) return 8;
      return 9;
   }
}


void TimeCalc()
{
   int n,N=10000000;
   int l=0;
   DWORD dwStart = GetTickCount();
   for( n = 1; n < N; n++ )
      l+= LenOfInt5( n );
   DWORD dwEnd =GetTickCount();
   cout << "l=" << l << ";  Time=" << dwEnd - dwStart << endl;
}

Оказалось, что первый (вроде как Ваш) работает неправильно. Время счёта для разных N:
N = 10000000: Вар1 – 9937, Вар2 – 578, Вар3 – 391, Вар4 – 187, Вар5 – 15
N = 200000000: Вар3 – 9062, Вар4 – 3234, Вар5 - 562
N = 2000000000: Вар4 – 30875, Вар5 – 5015

Это сообщение отредактировал(а) Ln78 - 13.5.2007, 16:19

W4FhLF

Дата 13.5.2007, 17:47 (ссылка)

(нет голосов)

Загрузка ...

found myself

Профиль
Группа: Участник Клуба
Сообщений: 2831
Регистрация: 2.12.2006

Репутация: 20
Всего: 121

Ln78, спасибо, что подняли такую интересную тему smile

У меня результаты таковы:

10000000:
LenOfInt1 - 218
LenOfInt2 - 719
LenOfInt3 - 290
LenOfInt4 - 170
LenOfInt5 - 67

1000000000:
LenOfInt1 - 22130
LenOfInt2 - 74718
LenOfInt3 - 35719
LenOfInt4 - 18029
LenOfInt5 - 7046

Но делать маленькие замеры с помощью GetTickCount неккоректно, поэтому для дальнейших тестов я решил выбрать число наибольшей разрядности, способное поместиться в DWORD - 1000000000.

Main:

Код


int main(int argc, char* argv[])
{
   int n,N=1000000000;
   int l=0;
   DWORD dwStart = GetTickCount();
   cout << LenOfInt6(10);
   for( n = 1; n < N; n++ )
      l+= LenOfInt6( n );
   DWORD dwEnd =GetTickCount();
   cout << "l=" << l << ";  Time=" << dwEnd - dwStart << endl;

    getche();
    return 0;
}

Из числа приведённых Вами самая быстрая LenOfInt5, но это не предел, взяв за основу LenOfInt5 получил такое вот:

Код


DWORD LenOfInt6 (DWORD n) 
{
    DWORD r = 0;
    __asm {
    mov eax,n
    mov ebx,10
    cmp eax,1000000000
    sbb ebx,0
    cmp eax,100000000
    sbb ebx,0
    cmp eax,10000000
    sbb ebx,0
    cmp eax,1000000
    jnc next
    sbb ebx,0
    cmp eax,100000
    sbb ebx,0
    cmp eax,10000
    sbb ebx,0
    cmp eax,1000
    sbb ebx,0
    cmp eax,100
    sbb ebx,0
    cmp eax,10
    sbb ebx,0
    next:
    mov r,ebx
    };
    return r;
}

Результат на 1000000000 - 3600.

Думаю не предел smile

PS Athlon 3500+ AM2

Добавлено @ 17:51
Идём дальше smile

Код


DWORD LenOfInt6 (DWORD n) 
{
    __asm {
    mov eax,n
    mov ebx,10
    cmp eax,1000000000
    sbb ebx,0
    cmp eax,100000000
    sbb ebx,0
    cmp eax,10000000
    sbb ebx,0
    cmp eax,1000000
    jnc next
    sbb ebx,0
    cmp eax,100000
    sbb ebx,0
    cmp eax,10000
    sbb ebx,0
    cmp eax,1000
    sbb ebx,0
    cmp eax,100
    sbb ebx,0
    cmp eax,10
    sbb ebx,0
    next:
    mov eax,ebx
    };
    return;
}

3400мс.

Добавлено через 10 минут и 51 секунду
advanced version smile

Код


DWORD LenOfInt8 (DWORD n) 
{
    __asm {
    mov eax,n
    mov ebx,10
    cmp eax,1000000000
    sbb ebx,0
    cmp eax,100000000
    jnc next
    sbb ebx,0
    cmp eax,10000000
    sbb ebx,0
    cmp eax,1000000
    sbb ebx,0
    cmp eax,100000
    jnc next
    sbb ebx,0
    cmp eax,10000
    sbb ebx,0
    cmp eax,1000
    sbb ebx,0
    cmp eax,100
    sbb ebx,0
    cmp eax,10
    sbb ebx,0
    next:
    mov eax,ebx
    };
    return;
}

2601мс. на 1000000000

Это сообщение отредактировал(а) W4FhLF - 13.5.2007, 17:52

--------------------

Ln78

Дата 13.5.2007, 20:13 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 274
Регистрация: 25.11.2006

Репутация: 13
Всего: 15

W4FhLF, я в ассемблере, особенно при работе с сопроцессором, не силён, поэтому для меня остались непонятными 2 вопроса: почему у меня результаты по первой функции так разительно отличаются по быстродействию и, что ещё хуже, по значению, причём последнее совсем непонятно. Так, если я перед циклом ставлю
cout << LenOfInt1(9);
а сам цикл считаю от 1 до 8, получаю, хоть и неправильный но «не сильно» ответ 11. А если строку с выводом комментирую (она, кстати, тоже выводит неправильный результат, равный 2), то получаю вообще -2147483636. Функцию я просто скопировал, непонятно, то ли в ней что-то не так, то ли где-то ещё. Среда – VS2005, процессор Intel Pentium-4, 3GHz. В чём может быть причина?

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »