Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / C++ [игнор отключен] [закрыт для гостей] / Как посчитать логарифи по основанию 2 в VC++6? / 14 сообщений из 14, страница 1 из 1
10.01.2005, 17:58
    #32857909
Serega128
Serega128
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как посчитать логарифи по основанию 2 в VC++6?
Как посчитать логарифи по основанию 2 в VC++6? Была у меня формула, да вот немогу найти, может кто так знает (с округлением до целого в большую сторону).
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.01.2005, 19:16
    #32857997
josia
josia
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как посчитать логарифи по основанию 2 в VC++6?
log x (y) - логарифм y по основанию x. Равен ln(y)/ln(x), где ln это любой логарифм. В VC++ 6 Вы можете использовать в качестве ln и log, и log10
Например: log(y)/log(2) или log10(y)/log10(2). Удачи
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.01.2005, 19:49
    #32858035
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как посчитать логарифи по основанию 2 в VC++6?
Для быстрого вычисления целочисленного логарифма есть неплохой алгоритмик, основанный на дихотомическом поиске. Если интересует... то могу поискать. Есть мнение что он работает быстрее чем вещественный. Хотя я сам не проверял.

P.S.

- Вы ведь сочувствуете голодающим детям?
- (...Кислярский сочувственно загрустил)

(с) 12 Стульев
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.01.2005, 09:57
    #32858393
Serega128
Serega128
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как посчитать логарифи по основанию 2 в VC++6?
>mayton
Конечно интересно, если не трудно, поищите плиз! Заранее благодарен.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.01.2005, 14:10
    #32861154
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как посчитать логарифи по основанию 2 в VC++6?
Вот. Кажется так. По аналогии можно написать функцию для short и long типов данных. Удобно реализовывать на ассемблере.

Для вычисление с избытком есть формула [Log2(x)]=Log2(x-1)+1

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
int Log2(unsigned int x){
	if (x== 0 ) return  32 ;
	n= 0 ;
	if (x<=0x0000FFFF) {n+= 16 ;x<<= 16 ;}
	if (x<=0x000FFFFF) {n+= 8 ;x<<= 8 ;}
	if (x<=0x00FFFFFF) {n+= 4 ;x<<= 4 ;}
	if (x<=0x3FFFFFFF) {n+= 2 ;x<<= 2 ;}
	if (x<=0x7FFFFFFF) {n+= 1 }
	return n- 31 ;
}

Пример приведен из книги Генри Уоррена "Алгоритмические трюки для программистов"
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.01.2005, 16:08
    #32861557
13th_apostle
13th_apostle
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как посчитать логарифи по основанию 2 в VC++6?
гмм... точность до целого при вычислении логарифмов? это рулит, imho, только при оценках. или я ошибаюсь?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.01.2005, 18:08
    #32861937
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как посчитать логарифи по основанию 2 в VC++6?
13th_apostleгмм... точность до целого при вычислении логарифмов? это рулит, imho, только при оценках. или я ошибаюсь?

Ну... это зависит от того что требуется реализовать. В криптографии поиск логарифма по основанию 2 и округление с избытком - это очень распространенная операция. Конечно можно сослатся на вычисления с плавающей точнкой... но вопрос в том, насколько это необходимо.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.01.2005, 18:24
    #32861977
Serega128
Serega128
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как посчитать логарифи по основанию 2 в VC++6?
>mayton
Он всё время -4 выводит.
Версия без ошибок такая:
int Log2(unsigned int x){
if (x==0) return 32;
int n=0;
if (x<=0x0000FFFF) {n+=16;x<<=16;}
if (x<=0x000FFFFF) {n+=8;x<<=8;}
if (x<=0x00FFFFFF) {n+=4;x<<=4;}
if (x<=0x3FFFFFFF) {n+=2;x<<=2;}
if (x<=0x7FFFFFFF) {n+=1;}
return n-31;
}
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.01.2005, 18:28
    #32861981
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как посчитать логарифи по основанию 2 в VC++6?
ОК. Я проверю сегодня вечером. С книжки переписал. Видимо очепятка.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.01.2005, 10:40
    #32862601
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как посчитать логарифи по основанию 2 в VC++6?
Вот. Была ошибочка в константе. И я думаю надо суффикс ul указывать. Тут разные компилляторы C++ ведут себя по разному. И int воспринимают по разному. Некоторые как 16 бит знаковое, некоторые 32.
Я тестировал на Borland C++ 5.4 Win32. Все нормально.

Исходник:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
#include <stdio.h>

int Log2(unsigned long x){
	if (x== 0 ) return - 1 ;
	int n= 0 ;
	if (x<=0x0000FFFFul) {n+= 16 ;x<<= 16 ;}
	if (x<=0x00FFFFFFul) {n+= 8  ;x<<= 8 ;}
	if (x<=0x0FFFFFFFul) {n+= 4  ;x<<= 4 ;}
	if (x<=0x3FFFFFFFul) {n+= 2  ;x<<= 2 ;}
	if (x<=0x7FFFFFFFul) {n+= 1  ;}
	return  31 -n;
}

int UpperLog2(unsigned int x)
{
	return Log2(x- 1 )+ 1 ;
}

void main()
{
	long x= 1 ;
	for(int i= 0 ;i< 12 ;i++){
		printf("[Log2(%u)] = %u\n",x,UpperLog2(x));
		x*= 5 ;
	}
}

Протокол работы:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
[Log2( 1 )] =  0 
[Log2( 5 )] =  3 
[Log2( 25 )] =  5 
[Log2( 125 )] =  7 
[Log2( 625 )] =  10 
[Log2( 3125 )] =  12 
[Log2( 15625 )] =  14 
[Log2( 78125 )] =  17 
[Log2( 390625 )] =  19 
[Log2( 1953125 )] =  21 
[Log2( 9765625 )] =  24 
[Log2( 48828125 )] =  26
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.01.2005, 11:57
    #32862833
MasterZiv
MasterZiv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как посчитать логарифи по основанию 2 в VC++6?
Это не логарифм по основанию два, а поиск единственной двоичной единицы в машинном слове. Да и чем сдвиги и маски городить, легче тупо проверить 33 значения.

А Log2(5) = 3 - этто оригинально !!
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.01.2005, 12:04
    #32862858
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как посчитать логарифи по основанию 2 в VC++6?
MasterZivДа и чем сдвиги и маски городить, легче тупо проверить 33 значения.


ОК. Давай сравнительный тест. Два варианта. С 5 проверками и с 33 проверками. И отчет о времени выполнения.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.01.2005, 12:09
    #32862873
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как посчитать логарифи по основанию 2 в VC++6?
MasterZivА Log2(5) = 3 - этто оригинально !!

Никакой ошибки нет. Для представления числа 5 достаточно 3 двоичных разрядов.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.01.2005, 12:10
    #32862877
13th_apostle
13th_apostle
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Как посчитать логарифи по основанию 2 в VC++6?
это зависит от того что требуется реализовать. В криптографии
сорри, я протупил: вопрос-то и был про округление до целого. =)
А Log2(5) = 3 - этто оригинально !!
так ведь так оно и есть при округлении в большую сторону.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / C++ [игнор отключен] [закрыт для гостей] / Как посчитать логарифи по основанию 2 в VC++6? / 14 сообщений из 14, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 520ms
Закрыть
start [/forum/topic.php?fid=57&mobile=1&tid=2033862]:
 0ms
get settings:
 10ms
get forum list:
 20ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 199ms
get topic data:
 14ms
get forum data:
 4ms
get page messages:
 66ms
get tp. blocked users:
 2ms
others: 197ms
total:  520ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]