17.03.2015, 23:58
|
 |
Профессор
|
|
Регистрация: 16.09.2009
Сообщений: 253
|
|
|
Заготовка для ассемблера: Извлечение корня
Занялся я алгоритмам возведения числа в квадрат и извлечения квадратного корня для 8-битной ЭВМ. Начал гуглить на эту тему, попалась статья для Z80. Однако, ожидаемого там не нашёл. Просто подготовка таблиц сложением нечётных чисел.
Взялся я в JS отладить собственный вариант.
Возведение в квадрат отладил, работает.
А вот извлечение корня - даёт сбой.
Причём, обе функции практически одинаковы, за исключением противоположных действий.
Помню, я долго искал в сети алгоритм нахождения точки пересечения двух отрезков. А когда написал сам, тогда и нашёл готовую.
Вот и сейчас, видимо, плохо ищу...
Тут используется умножение, Вообще не подходит.
Если можете, помогите...
<html>
<script>
function square(n) {
var
m = 1, // Mask
r = 1, // Result
t = n, // Temp
h, // 1/2 of square
q; // 1/4 of square
if(!n)
return 0;
while(t >>= 1)
m <<= 1, r <<= 2;
h = r >> 1, q = h >> 1;
while(m >>= 1) {
if(n & m)
r += h + h + q, h += q;
h >>= 1, q >>= 2;
}
return r;
}
function root(n) {
var
m = 1, // Mask
r = 0, // Result
s = 0; // Shift
++ n;
while(n >> (s + 1))
++ s;
m <<= s & -2;
do {
s = r + m, r >>= 1;
if(s < n)
n -= s, r |= m;
} while(m >>= 2);
return r;
}
function squares(m, n) {
var
i, s, r, d = [];
for(i = m; i <= n; ++ i) {
s = square(i);
r = root(s)
if(i != r)
d.push(i + "<sup>2</sup>=" + s + "<sup><sup>1/2</sup></sup>=" + r);
}
return d;
}
function main() {
document.getElementsByTagName("pre")[0].innerHTML = squares(0,100).join("<br>");
}
</script>
<body onload='main()'>
<pre>
</pre>
</body>
Последний раз редактировалось Paguo-86PK, 19.03.2015 в 08:55.
Причина: Вылечил алгоритм
|
|
18.03.2015, 05:07
|
|
Профессор
|
|
Регистрация: 14.01.2015
Сообщений: 12,989
|
|
Ник 
Описаний алгоритмов в сети как раз куча, если вы знаете ассемблер, то взять алгоритм ассемблера 32-бит, и перевести его на 8-бит, не является проблемой.
Более того, есть способ извлечения корня "столбиком" (в сети тоже найдете), это способ переложить на ассемблер не сложно. А еще, если "для изучить" пример, то в среде для конкретного процессора пишем на Си, а полученный в конечном итоге HEX-дамп дизассемблирем. Изучаем ) |
|
18.03.2015, 14:27
|
|
Профессор
|
|
Регистрация: 16.09.2009
Сообщений: 253
|
|
|
Заготовка для ассемблера: Извлечение корня
Сообщение от laimas
|
Ник
Описаний алгоритмов в сети как раз куча, если вы знаете ассемблер, то взять алгоритм ассемблера 32-бит, и перевести его на 8-бит, не является проблемой.
Более того, есть способ извлечения корня "столбиком" (в сети тоже найдете), это способ переложить на ассемблер не сложно. А еще, если "для изучить" пример, то в среде для конкретного процессора пишем на Си, а полученный в конечном итоге HEX-дамп дизассемблирем. Изучаем )
|
Вы не поверите и будете смеяться 
Данный выше алгоритм я придумал графически, так как с математикой у меня достаточно туго. Я просто вообразил квадрат из шаров и нашёл метод дополнить их недостающими шарами.
Т.е. играл воображением, а не вычислениями.
Поэтому, возведение в квадрат у меня работает. А извлечение корня - нет. Просто, я не могу найти именно математическую ошибку. Т.к. извлечение корня строил тоже по графическому алгоритму.
Вот иллюстрация: |
|
18.03.2015, 16:15
|
 |
junior
|
|
Регистрация: 29.11.2011
Сообщений: 3,924
|
|
|
Сообщение от Paguo-86PK
|
Возведение в квадрат отладил, работает.
А вот извлечение корня - даёт сбой.
|
все вокруг возведения в степень вертится
Math.pow(9, 1/2); // квадратный
Math.pow(27, 1/3); // кубический
Math.pow(81, 1/4); // ху*ческий
__________________
Чебурашка стал символом олимпийских игр. А чего достиг ты?
Тишина - самый громкий звук
Последний раз редактировалось nerv_, 18.03.2015 в 16:21.
|
|
18.03.2015, 16:58
|
|
Профессор
|
|
Регистрация: 14.01.2015
Сообщений: 12,989
|
|
Можно и посмеяться. Только если речь идет о 8-бит процессоре, то каким боком тут JavaScript вам поможет, неужто вы и браузер под нее писать будете?
Алгоритм извлечения квадратного корня, ассемблер. Это не для 8-бит, но это дает представление о решениях. Переложить этот ассемблер на 8-бит для того же Z80 можно.
На Си - sqrt(double).
Z80 это тот же i80, но с интересной особенностью - второй набор регистров, между которыми можно переключаться. Если программировать для 8-бит ЭВМ, к примеру 80С51, значит надо брать ее среду разработки. JS в эту среду ну никак не входит, и какая от него польза в этом контексте не понимаю. ) |
|
18.03.2015, 17:25
|
|
Профессор
|
|
Регистрация: 16.09.2009
Сообщений: 253
|
|
|
Заготовка для ассемблера: Извлечение корня
|
Сообщение от laimas
|
Можно и посмеяться. Только если речь идет о 8-бит процессоре, то каким боком тут JavaScript вам поможет, неужто вы и браузер под нее писать будете?
Алгоритм извлечения квадратного корня, ассемблер. Это не для 8-бит, но это дает представление о решениях. Переложить этот ассемблер на 8-бит для того же Z80 можно.
На Си - sqrt(double).
Z80 это тот же i80, но с интересной особенностью - второй набор регистров, между которыми можно переключаться. Если программировать для 8-бит ЭВМ, к примеру 80С51, значит надо брать ее среду разработки. JS в эту среду ну никак не входит, и какая от него польза в этом контексте не понимаю. )
|
Ну, я кажется в названии тему подчеркнул "Заготовка" для ассемблера.
Т.е. JS алгоритм расписал так, будто переменные - регистры. И их можно только сдвигать, складывать и маскировать.
Причём, сейчас я учусь писать на Verilog, а там и вовсе регистры двигать не надо - только проводники (Wire) смещаешь.
Данная тема ещё к тому, что 17 лет назад разрабатывал (в уме, тетради) множитель 32-битных чисел (без тактирования) на ТТЛ-логике. Т.е. тупо, 32 штуки 32-битных сумматоров + 32 мультиплексора. Получилось что-то около 20 миллионов транзисторов (1 бит сумматора ~42 транзистора). Схема работает (в уме) без тактов: Подаёшь операнды X и Y, тут же снимаешь их произведение без стробирования.
Тогда я думал, что возвести в квадрат без умножения нельзя. А извлечь квадратный корень - тем более! Т.е. тактировать надо.
Если Вы понимаете, то Verilog-схему очень тяжело отлаживать. Легче расписать всё на Си или JS, отладить, отловить баги. А потом перевести на язык ассемблера i8080/Z80 или описать в Verilog.
Причём, средства Verilog позволяют какрас сдвиг регистров заменить на сдвиг проводников. Т.е. вместо 32 тактов можно воспроизвести 32 копии одного узла со смещением проводков на 1/2 бита. И схема уже без тактовой частоты выдаст квадратный корень целого числа.
Надеюсь, теперь более-менее ясно, зачем я на JS пишу то, что хочу написать на 8-битном процессоре? А потом перевести и в ПЛИС через Verilog. Просто, JS - самый доступный инструмент и я его достаточно знаю. Если бы я сразу бы взялся писать на Z80 - повесился бы.
Ведь в JS можно всё собирать в логи. Каждый шаг...
Вот...
А у меня эта функция извлечения корня хондрит. И не понимаю, почему...
P.S.: Алгоритм извлечения квадратного корня, ассемблер помог, Спасибо за ссылку.
Правда, я не понимаю, как он работает. Т.е. да, в Visual Studio в отладке всё по шагам вижу, но не понимаю принцип. Свой (на JS выше) я написал сам и представляю, как он действует. А этот, готовый, вроде бы и похож на мой... Сдвиги, сумма и т.д.
Короче, надо копаться.
Последний раз редактировалось Paguo-86PK, 18.03.2015 в 17:44.
|
|
18.03.2015, 18:18
|
|
Профессор
|
|
Регистрация: 14.01.2015
Сообщений: 12,989
|
|
|
Нет, на Verilog я не писал, не знаю его, поэтому и недоразумение, и даже не представляю как нужно представить алгоритм на JS, который в последствии нужно будет перенести на Verilog.
Где-то у меня на CD еще хранится все что собирал и под процессоры, и под контроллеры, а среда разработки это Си и Ассемблер, отладчики, программаторы. Не выбросил, есть там и библиотеки различные, а в среде разработки можно было произвести подключения и машинного кода, так что проблем не было. А под Verilog нет библиотек?
И не повесился когда писал, первый раз для Z80 (правда к этому времени я хорошо знал i80), все сразу на том что есть, даже непонятное приходилось отлаживать, следя за состоянием аккумулятора, стека и регистров.
На Радио-86РК в нашей стране выросло не мало спецов в вычислительной сфере, а нынешнее положение с компьютерами порождает спецов игры в танчики. Случайно попался в руки контроллер от старой РС японской на Z80, выдрал его, оказался цел. На нем собрал MIDI клавиатуру по материалам журнала РАДИО, взята была идея. Но захотелось большего чем там было, регулировать атакой и затуханием звука, контроль силы нажатия клавиш. Стало понятным, что на одном Z80 все не получится. Вот тогда я впервые и столкнулся с однокристальными ЭВМ. И заболел. Далее уже на заказ - охранные устройства, примочки разные для охотников и рыбаков, системы контроля и т.п.
Потом опять резкий поворот, и опять по воле случая, и теперь занимаюсь тем, чем занимаюсь, все прошлое на CD и покрывается пылью. )
Последний раз редактировалось laimas, 18.03.2015 в 18:21.
|
|
18.03.2015, 18:32
|
 |
Профессор
|
|
Регистрация: 24.09.2013
Сообщений: 1,436
|
|
|
Сообщение от nerv
|
Math.pow(81, 1/4); // ху*ческий
|
Тессерактовый?
Последний раз редактировалось Erolast, 18.03.2015 в 18:34.
|
|
18.03.2015, 19:42
|
|
Профессор
|
|
Регистрация: 14.01.2015
Сообщений: 12,989
|
|
в Visual Studio в отладке всё по шагам вижу, но не понимаю принцип.
А что смотрим? Это же ассемблер, значит надо знать команды, а остальное и в уме представить можно - ток медленно перетекает из регистра В в регистр С
|
|
18.03.2015, 19:43
|
|
Профессор
|
|
Регистрация: 16.09.2009
Сообщений: 253
|
|
|
Заготовка для ассемблера: Извлечение корня
|
Сообщение от laimas
|
|
Нет, на Verilog я не писал, не знаю его, поэтому и недоразумение, и даже не представляю как нужно представить алгоритм на JS, который в последствии нужно будет перенести на Verilog.
|
У меня есть диск "Инженеру-электронщику" с OrCAD 10. Там есть утилиты для перевода Java-программ в VHDL/Verilog. Так что, вручную вполне можно из JS перенести и в Verilog, если опыт есть... Вернее, желание набраться опыта...
|
Сообщение от laimas
|
|
Где-то у меня на CD еще хранится все что собирал и под процессоры, и под контроллеры, а среда разработки это Си и Ассемблер, отладчики, программаторы. Не выбросил, есть там и библиотеки различные, а в среде разработки можно было произвести подключения и машинного кода, так что проблем не было. А под Verilog нет библиотек?
|
Как уже сказал, есть конверторы Java-to-VHDL, но старые. Т.к. компания-разработчик разорилась. Один спец по аппаратуре был удивлён и не поверил мне, что есть такие конверторы. А когда увидел, сказал, что уже устарело 10 раз (как Watcom-C), не поддерживается. Потому и не все знают...
|
Сообщение от laimas
|
|
И не повесился когда писал, первый раз для Z80 (правда к этому времени я хорошо знал i80), все сразу на том что есть, даже непонятное приходилось отлаживать, следя за состоянием аккумулятора, стека и регистров.
|
20 лет тому назад, когда я отыскал под ZX gens48/mons48, очень обрадовался. Но бесило, что для редактирования дампа нужно грузить 5 минут редактор.
|
Сообщение от laimas
|
|
На Радио-86РК в нашей стране выросло не мало спецов в вычислительной сфере, а нынешнее положение с компьютерами порождает спецов игры в танчики.
|
Потому и ZX у меня не прижился. На нём была куча игр, а прикладных на рынке туго было найти.
А на Радио-86РК всё тупо: Нажал СБРОС, набрал директивы D/M монитора, и весь дамп памяти у тебя в руках (без всяких Gens48). Я им пользовался до 1998, пока не сел за "Поиск" с DOS 3.11.
Будете смеяться, но программирую на РК до сих пор: вот и вот. Причём, написал свой ассемблер в духе x86-синтаксиса:
|
Код:
|
mov a,a -> mov al,al
mov m,c -> mov [bx],cl
cma -> not a
lhld adr-> mov bx,[adr] |
И пишу свою оконную функцию API. Вместо F809... Вроде бы работает...
|
|
|
|
