lamerok 0 25 декабря, 2004 Опубликовано 25 декабря, 2004 · Жалоба У меня такая проблема. Кварц 32768. Проц должен за 300 мс найти корень из целого числа (X) в диапазоне от 625 до 10000. Нужно получить корень но с точностью два занака, т.е например, корень(1000)= 31.62 = (3162) Беру следующим образом (итеррациями): Если (X<=2500) то итерации такие (y1 =) y + (X - y^2) Если (X>2500), то такие (y1 =) y + (X - y^2)/2. Вроде считает правильно, но самое максимальное получается 13 итераций. в итоге занимает примерно 850 мс. Очень долго. Посмотрел, оказалось, что больше всего занимает место перемножение двух 16 рарядных целых чисел(квадрат y^2). примерно 450 циклов в каждой итеррации. Не подскажите как можно квадрат сделать в циклов 100. или как корень побыстрее сделать. Использую PIC16. Пробывал по другому do // { // a = b; // b = (a + c/a)/2; // } while (a > b); Получается секунды 2. Из-за того, что все числа long int; Заранее спасибо typedef unsigned char tU8; /* 8 bits, unsigned */ typedef signed char tS8; /* 8 bits, unsigned */ typedef unsigned int tU16; /* Two-byte unsigned int */ typedef long int tS32; typedef signed int tS16; /* Two-byte signed int */ typedef unsigned long tU32; /* Four-byte unsigned */ typedef union {tU8 Byte[4]; tS16 I[2]; tU32 L;} tAll; tS16 Sqrt(tS16 value) { tAll a; tS16 b; tU8 c; tAll temp; { // c = 10000; // c = c*Result; // b = c; // do // { // a = b; // b = (a + c/a)/2; // } while (a > B); // } // Result = a; // return Result; c = value>>8; /*Выделяем старший байт*/ a.L = value * 429496; /* домнажаем на 65556*6.5536 для точности */ b = 1; temp.I[0] = a.I[1]; temp.I[1] = a.I[1]; while(b>0) { a.L = (tU32)temp.I[0]*(tU16)temp.I[0]; /* y^2 */ b = (temp.I[1] - a.I[1]); /* X - y^2 */ if (c > 9) /* Если больше чем 0x900 */ { b =b>>2; /* (X - y^2)/2 */ } temp.I[0]+=b; /* y = y+(X-y^2) или y = y+(X-y^2)/2*/ }; } a.L = (tU32)temp.I[0] * 10000; /* Множим на 65536/6.5536 = 10000*/ return a.I[1]; /* В старшем байте искомый результат */ } Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
yornik 0 26 декабря, 2004 Опубликовано 26 декабря, 2004 · Жалоба Есть метод извлечения корня "в столбик". Если Вам нужно 16 бит результата, то будет 16 итераций с вычитаниями/сравнениями (почти как деление). Должно быть быстрее, по идее. Мы аппаратуру свою такую делали (а потом корки такие появились :) ) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
lamerok 0 27 декабря, 2004 Опубликовано 27 декабря, 2004 · Жалоба Практически так и сделал... взял пример c форума микрочипа... Получилось быстрее почти в 8 раз, теперь занимает всего 900 циклов корень от значения в диапазоне от 0 до 10000. Вот чего получилось... tS16 Sqrt(tS16 value) { tS16 Result; tU32 ulinput; // вход 27 бит tU16 uitemp; // результат, и врем. tU8 ucc; // счетчики /* uniput = (value*10000) Для точности 2 знака */ ulinput = value<<1; ulinput += (tU32)value<<3; ulinput = ulinput<<1; ulinput += ulinput<<2; ulinput = ulinput<<1; ulinput += ulinput<<2; ulinput = ulinput<<1; ulinput +=ulinput<<2; /*********************Конец умножения на 10000 *********************/ Result = 0; uitemp = 0; ucc = 14; do { uitemp <<= 1; if (ulinput & 0x08000000) uitemp |= 1; ulinput <<= 1; Result <<= 1; uitemp <<= 1; if (ulinput & 0x08000000) uitemp |= 1; ulinput <<= 1; Result <<= 1; Result &= ~2; // set '01' at the end Result |= 1; if (uitemp >= Result) { uitemp -= Result; Result |= 2; } Result >>= 1; } while (--ucc != 0); // конец циклов return Result; } Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
olefil 0 27 декабря, 2004 Опубликовано 27 декабря, 2004 · Жалоба Врядли быстрее сделаешь математика вещь жесткая (хотя хрен знает) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
yornik 0 28 декабря, 2004 Опубликовано 28 декабря, 2004 · Жалоба 2 lamerok: а почему именно на 10000 умножаете? Не проще ли просто сразу входное число дополнять шестнадцатью бинарными нулями (т.е. умножать на 65536) ? Масштабирование результата в 256 раз учесть, имхо, не сложнее, чем в варианте с масштабированием в 100 раз. Кусок из "Алгоритмические трюки для программистов" (!не пробовал сам!), для 32-битного исходного числа, "в среднем ему требуется 149 базовых RISC-команд": int isqrt (unsigned x) { unsigned m, y, b; m = 0x40000000; y = 0; while (m != 0) { //16 раз b = y | m; y = y >> 1; if (x >= b) { x = x - b; y = y | m; } m = m >> 2; } return y; } Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
YuryL 0 28 декабря, 2004 Опубликовано 28 декабря, 2004 · Жалоба Интересная статья по вычислению корня квадратного с ракурсом в историю аж до арифмометров. Integer Square Roots by Jack W. Crenshaw http://www.embedded.com/98/9802fe2.htm Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Joseph 0 29 декабря, 2004 Опубликовано 29 декабря, 2004 · Жалоба Господа, а не проще ли табличными методами? Память сейчас дешевая... :) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться