forum.boolean.name

forum.boolean.name (http://forum.boolean.name/index.php)
-   Алгоритмика (http://forum.boolean.name/forumdisplay.php?f=21)
-   -   Любопытные формулы (http://forum.boolean.name/showthread.php?t=275)

impersonalis 01.11.2005 20:29
Напрмер.
Реализация чередования значений a и b, хранящийхся в перменной x
x=( a + b ) - x
Перед первой обработкой в x должно хранится одно из значений (a или b )
Код:
a=6
b=9
x=b
For i=1 To 10
        x=(a+b)-x
        Print x
Next
WaitKey()

impersonalis 01.11.2005 20:36
Реализация прохода переменной x всех значений из [0;b-1]
x = ( x + 1 ) Mod b
Код:
b=5
x=0
For i=1 To 10
        x=(x+1)Mod *b
        Print x
Next
WaitKey()

impersonalis 01.11.2005 20:46
Выбор максимума из a,b в одну ф-лу
x = ( Abs( a-b ) + ( a+b ) ) *.5
Код:
a=4
b=10
x=(Abs(a-b)+(a+b))*.5
Print x
WaitKey()

jimon 01.11.2005 23:58
хм

ето ты сам придумал ? или где взял ?

НУБ 02.11.2005 01:44
>Выбор максимума из a,b в одну ф-лу
>x = ( Abs( a-b ) + ( a+b ) ) *.5

If a>b
x=a
else
x=b
endif

- это будет гораздо быстрее, чем куча умножений/сложений(раз в 5-6 примерно), вот тест(если не верите):

Код:
a=5
b=8

time1=MilliSecs()
For i=1 To 10000000
x = ( Abs( a-b ) + ( a+b ) ) *.5
Next
time1=MilliSecs()-time1

time2=MilliSecs()
For i=1 To 10000000
If a>b
x=a
Else
x=b
EndIf
Next
time2=MilliSecs()-time2


Print time1
Print time2
WaitKey()

jimon 02.11.2005 16:34
прикол у меня первый способ быстрее :)
у pentiumов alu рулит полюбе - вот за что их люблю , и неглючат никогда

impersonalis 02.11.2005 20:55
Не отрицаю - все выше изложенные формулы работают медленее, конструкций условного перехода, однако, в борьбе за скорость приходится отказваться от удобочитаемости ( избавляться от функциий, юзать goto и т.п.) - так что выбор за вами. Я лишь посчитал эти формулы интересными.
Практически все где-то видел : в институте, интернете, чужом коде.

impersonalis 02.11.2005 20:58
Ф-лу минимума можно получить или эвристически или объединив ф-лы для max и чередования 2ух значений.
x = ( ( a+b ) - Abs( a-b ) ) *.5
Код:
a=10
b=1
x = ( ( a+b ) - Abs( a-b ) ) *.5
Print x
WaitKey()

alcoSHoLiK 23.01.2006 23:01
Как определить, является ли число степенью двойки?
Код:
bool PowOfTwo (int num)
{
  return !(num & (num-1));
}

jimon 24.01.2006 14:33
БЫСТРЫЙЙЙЙ !!! :)) квадратный корень с минимальной точностью

Код:
float fast_sqrt(float f)
{
  float result;
  _asm
  {
    mov eax, f
    sub eax, 0x3f800000
    sar eax, 1
    add eax, 0x3f800000
    mov result, eax
  }

  return result;
}
:))

impersonalis 24.01.2006 15:39
2jimon :
продолжая борьбу за скорость: добавь ещё inline для функции

alcoSHoLiK 24.01.2006 22:11
Да, хорошая функция, но огорчает, что выдает неточный результат с простыми корнями. Например, fast_sqrt(625)==25.76, а fast_sqrt(144)==12.5.

jimon 24.01.2006 23:05
ето не я делал... щитается дефак-то самая быстрая функция примерного извлечение квадратного корня

alex-mad 25.01.2006 00:05
Цитата:
Originally posted by jimon@Jan 24 2006, 10:05 PM
ето не я делал... щитается дефак-то самая быстрая функция примерного извлечение квадратного корня
а говорил с минимальной точностью...

jimon 25.01.2006 19:10
ну всеже она может хоть чучуть сказать какой корень :)

alex-mad 25.01.2006 20:35
Цитата:
Originally posted by jimon@Jan 25 2006, 06:10 PM
ну всеже она может хоть чучуть сказать какой корень :)
гы... нафиг такое надо? ф топку!

Kain 25.01.2006 23:10
Может я ещё не опоздал ?
alcoSHoLiK
Цитата:
Как определить, является ли число степенью двойки?
если я понял правильно, то ето можно решить так :
Цитата:
перевести число в Bin и одна проверка
при одной 1 (может слова не те )
True
правые 0 откинуть, левые : степень, для 2 .
ещё можно такой способ, не только для двойки
(а вернее для не степени двойки оснований ) :
Цитата:
1)извлекаем кв.корень
2)проверяем на целосность (вроде натуральное называется)
True
3)делим число на основание
4)проверяем на целосность
Return true
False
Меняем 1) и 3) местами
подумаю ещё над приоритетом 1)2)3) и 3)2)1)
про узнавании степени не додумал ,пока.

PS ещё про корни :
где-то в древности корень примерно извлекали так
Код:
sqr(a)=sqr(b^2+c)~b+(c/2b)

где
B^2 > С
чем больше
тем точнее
Описал I в.н.э. древнегреческий ученый Героном Александрийский

alex-mad 26.01.2006 01:28
to Kain
в формулу корня особо не вникал, но она не пригодится, т.к. в правой части всё равно есть корень... время не выиграем... так што можно считать как обычно ( что не на много быстрее)
алгоритмы - это конечно хорошо, но тут вроде как "Любопытные формулы"
и к тому же alcoSHoLiK уже написал формулу "проверка числа на степень 2":
Код:
bool PowOfTwo (int num)
{
 *return !(num & (num-1));
}

Kain 26.01.2006 22:46
Формула не для пользования была приведена, а для справки
так считали 4000 лет назад....
учебник Алгебры 8 класса

1)у alcoSHoLiK 'а стоит знак вопроса
2)ето не для блица (тупо посмотрел справку,нету там :lol:

а так как я не профи, как понял так и ответил
а вообще когда есть двусмысленность пишите как impersonalis:
ответ (читать ... ... .. )

N.O.T. 07.02.2007 11:29
Re: Любопытные формулы
 
Нужно было догнать любое число до первого большего с основанием 2 в N-степени, пример: если число 31, то резалт должен быть 32, если 257, то 512 и т.д.
Сначала написал, чтоб посмотреть будет ли ваще програ раобтать простым циклом:
while(true)
{
static int iIter = 1;
if( iLabelWidth > iIter )
iIter = iIter << 1;
else
{
iLabelWidth = iIter;
break;
}
}
потом начал придумывать как моно сделать запись короче, придумал:
// fIn - вход. число
// получаем степень
float stepen = log10((float)fIn)/ log10(2.0f);
int res = pow(2, ((floor(stepen)+1)));
Результат при сравнении на быстродействие:
на 10 млн. итераций выполняется за 9284 мск, против первого(обычным циклом) за 50 мск.
Так что оставил первый. Может кто-то лучше напишет, вставлю себе.

impersonalis 18.10.2007 15:55
Re: Любопытные формулы
 
Код:
((char*)&w)[sizeof(w)-1]&=~(1<<7);
Где w - float или double. Зануляет знаковый бит числа - аналог fabs. Не претендую на скорость выполнения - просто извращённая формула, порождённая моим мозгом.

HolyDel 26.12.2007 13:11
Re: Любопытные формулы
 
Цитата:
((char*)&w)[sizeof(w)-1]&=~(1<<7);
интересно, компилятор ~(1<<7) рассчитает как константу? или в рантайме будет это считать?

jimon-у спасибо за быстрыыыыый корень.
2Imeprsionalis - inline не получится вставить. там код на asm-e.

alcoSHoLiK 26.12.2007 19:14
Re: Любопытные формулы
 
Константные выражения компилятор считать умеет. Если не доверяешь ему, смотри сгенерированные асм-листинги.

impersonalis 04.10.2008 23:42
Ответ: Любопытные формулы
 
<<jimon>> (23:32:19 4/10/2008)
http://www.graphics.stanford.edu/~seander/bithacks.html канопляное поле - единство битовой вселенной !

~Lexx~ 17.11.2009 08:54
Ответ: Любопытные формулы
 
Формула для возведения числа в любую степень и извлечения любого корня:

exp(b*ln(a)),

где a - число, которое возводим в степень, b - степень в которую возводим, exp - экспонента, ln - натуральный логарифм.

cheaters-hater 09.02.2010 16:42
Ответ: Любопытные формулы
 
формула возвращает 0 если (параметр<0) или параметр, если (параметр=>0)
result= ( parameter+Abs(parameter) )/2
понадобилось при прохождении массива по элементам, во избежание минусовых индексов.
не самый быстрый и правильный вариант решения задачи, но может кому пригодится.:)

ABTOMAT 09.02.2010 19:33
Ответ: Любопытные формулы
 
result = parameter*(parameter>0) , не?

IGR 09.02.2010 22:56
Ответ: Любопытные формулы
 
если учитовать строго условие то по задумке
result = parameter*(parameter>=0) :)

impersonalis 10.02.2010 05:02
Ответ: Любопытные формулы
 
Цитата:
Сообщение от ABTOMAT (Сообщение 136696)
result = parameter*(parameter>0) , не?
Автор же написал:
Цитата:
не самый быстрый и правильный вариант решения задачи
Здесь не мало примеров формул нерациональных, но любопытных.
Думаю - стоит перместить тред в Математику (там она будет более к месту, не смущая брейнфачными решениями).

Alex.D. 10.02.2010 07:22
Ответ: Re: Любопытные формулы
 
Цитата:
Сообщение от N.O.T. (Сообщение 31299)
Нужно было догнать любое число до первого большего с основанием 2 в N-степени, пример: если число 31, то резалт должен быть 32, если 257, то 512 и т.д.

Может кто-то лучше напишет, вставлю себе.
Код:
x -= 1;
x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
x += 1;
^__^

ABTOMAT 10.02.2010 20:38
Ответ: Любопытные формулы
 
>> 30
Матан-нази негодует!

Igor 22.05.2010 15:51
Ответ: Любопытные формулы
 
Поиск корня из числа "а" любой степени точности:
прикидываем примерный корень - "b"
(Где-то выше по форуму есть такой алгоритм)
с:=a/b
b:=(c+b)*0.5
Повторяем две предыдущие операции до достижения желаемой точности (2-4 раза достаточно)
P.S. По-моему, это называется формулой Ньютона


Часовой пояс GMT +4, время: 01:16.

vBulletin® Version 3.6.5.
Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
Перевод: zCarot