roboforum.ru

Технический форум по робототехнике.

blindman - [Как возвести 2 в степень n?]

Блоги посетителей.
Правила форума
В данном разделе каждый может иметь не более одной темы. Тема должна начинаться с логина (ника) робофорума.

Re: blindman - [Даташиты надо читать!]

Сообщение avr123.nm.ru » 19 июн 2011, 15:10

Странно как-то. http://www.silabs.com/Support%20Documen ... cp2102.pdf

Supply Voltage
- Self-powered: 3.0 to 3.6 V
- USB bus powered: 4.0 to 5.25 V
Читайте !
Аватара пользователя
avr123.nm.ru
отсылающий читать курс
 
Сообщения: 14195
Зарегистрирован: 06 ноя 2005, 04:18
Откуда: Москва
Предупреждения: -8

Re: blindman - [Даташиты надо читать!]

Сообщение blindman » 19 июн 2011, 15:24

Ага. Bus-powered - это когда от USB берется питание и через стабилизатор на VDD подается
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

Re: blindman - [Даташиты надо читать!]

Сообщение Michael_K » 19 июн 2011, 16:01

Там, мне казалось, стабилизатор встроенный, но, конечно, это предусмотреть на плате надо...
А не вариант что-нить в районе 6-7 ноги отрезать-коротнуть?
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

Re: blindman - [Даташиты надо читать!]

Сообщение blindman » 19 июн 2011, 16:37

Да ну его, долбаться. Там питалово еще кроме самой микросхемы еще на резистор подтяжки идет (читалка iButton). Это надо будет 2 дороги порезать, замкнуть 2 вывода QFN - к одному из которых проводники не подведены совсем, и кинуть проводок. При этом еще и выход стабилизатора без блокировочного конденсатора останется. Если бы для себя, в единственном экземпляре - поставил бы внешний стабилизатор, и все дела. А так проще переделать, тем более что те платы, что уже есть, не пропадут, пойдут в дело. На плате разведены по сути 2 отдельных устройства - у них корпуса одинаковые.
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

Re: blindman - [Даташиты надо читать!]

Сообщение dccharacter » 19 июн 2011, 18:23

Писал же! forum14/topic9235.html
Мой волшебник это я сам. Всю архитектуру программы придумал лично, а ребята помогли воплотить её. Я бы и сам мог написать, но лень учить язык и его конструкции.
Аватара пользователя
dccharacter
 
Сообщения: 4995
Зарегистрирован: 10 дек 2010, 13:16
Откуда: Красногорск МО
прог. языки: C, Python, wiring/processing
ФИО: Андрей

Re: blindman - [Опитамальный алгоритм умножения?]

Сообщение blindman » 15 июл 2011, 11:37

Дано : произвольное целое число x со знаком, целая константа k со знаком. Необходимо вычислить y = kx, используя только операции арифметического сдвига, сложения и вычитания, за минимальное количество операций. Пусть k = -14, тогда простейшее решение "в лоб" y = -(x << 1) - (x << 2) - (x << 3). Но оптимальным будет : y = (x << 1) - (x << 4). Вопрос в том, как найти это оптимальное сочетание сдвигов, сложений и вычитаний для заданного k? Может существует какой-то формальный алгоритм?
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

Re: blindman - [Опитамальный алгоритм умножения?]

Сообщение =DeaD= » 15 июл 2011, 11:56

Конечно существует. Только задачу надо избавить от X:

Дано произвольное k - целое, надо выразить его через сумму минимального количества элементов вида +\-2^(целое неотрицательное).

=====================================================================

Сначала 2 леммы:

Пусть n - такое максимальное, что 2^n<=|k|.

Вроде несложно показать, что:
1. Не нужны слагаемые в степени более чем n+1.
2. Как минимум нужно слагаемое в степени n.

=====================================================================

Теперь пусть мы знаем все правильные решения для |k|<z.

Попробуем найти решение R(z) для z (для -z получим очевидным образом инвертировав знаки):
Если z=2^n, тогда решение очевидно, иначе из двух лемм вроде очевидным образом вытекает, что оптимальное решение R(z) это либо 2^n+R(z-2^n), либо 2^(n+1)-R(2^(n+1)-z), заметим, что |z-2^n|<z и |2^(n+1)-z|<z.

Бинго!

Добавлено спустя 42 секунды:
Ну а реализация в софте - либо динпрог, либо перебор, тут уж смотря какие требования к производительности и наличию времени на кодинг.
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: blindman - [Опитамальный алгоритм умножения?]

Сообщение boez » 15 июл 2011, 12:40

=DeaD= писал(а):Ну а реализация в софте - либо динпрог

Это я так понимаю, если народ умными словами не пугать, просто рекурсия - из функции R(z) вызываем R(2^(n+1)-z) и R(z-2^n) и смотрим, какое решение оптимальнее? Ну а R(0) и R(+-1) возвращают константные решения, так?
boez
 
Сообщения: 1981
Зарегистрирован: 27 авг 2008, 10:45
Откуда: Харьков
прог. языки: С/С++

Re: blindman - [Опитамальный алгоритм умножения?]

Сообщение blindman » 15 июл 2011, 12:57

Просто рекурсия - это перебор. Немного оптимизировать можно применив кэширование.

Динпрог - [[ru:Динамическое программирование]]

Добавлено спустя 7 минут 34 секунды:
Антон, спасибо! Отлично работает метод.

В дополнение - если m - минимальное неотрицательное целое, такое что |k| < 2^m, количество элементов решения не превышает (m >> 1) + 1
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

Re: blindman - [Опитамальный алгоритм умножения?]

Сообщение Michael_K » 15 июл 2011, 15:47

blindman писал(а):Необходимо вычислить y = kx, используя только операции арифметического сдвига, сложения и вычитания, за минимальное количество операций.

=DeaD= писал(а):Дано произвольное k - целое, надо выразить его через сумму минимального количества элементов вида +\-2^(целое неотрицательное).


Имхо такая формулировка - существенное упрощение задачи.

Например, чтобы умножить на 0x66
проще сначала умножить на 6 и запомнить результат, а потом полученное умножить еще на 16 и сложить с запомненным.

То есть делаем не четыре сдвига и четыре сложения, а три сдвига и три сложения, но используем лишнюю ячейку памяти для промежуточного результата.
Ну и с минусами так же - просто примеры не столь очевидные.
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

Re: blindman - [Опитамальный алгоритм умножения?]

Сообщение =DeaD= » 15 июл 2011, 16:14

Согласен, значительно упростил, тут получается такой эффект:

0x66=102=64+32+4+2=(16+1)(4+2)

Значит если z не простое, тогда кроме 2^n+R(z-2^n) и 2^(n+1)-R(2^(n+1)-z) надо еще перебрать все R(q)*R(z/q), где q - один из делителей z не равный 1 и меньший или равный sqrt(z) :pardon:
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: blindman - [Опитамальный алгоритм умножения?]

Сообщение Michael_K » 15 июл 2011, 16:16

такие формулы я не понимаю - это для меня слишком сложно :) и лениво...
может быть проще на множители раскладывать... только вот не всегда оптимум получится. Его нужно как-то отдельно оценивать... И правда перебором что-ли...
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

Re: blindman - [Опитамальный алгоритм умножения?]

Сообщение =DeaD= » 15 июл 2011, 16:19

А R(q)*R(z/q) это и есть раскладывание на множители :)
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: blindman - [Жара!!!]

Сообщение blindman » 09 окт 2011, 18:15

Код: Выделить всёРазвернуть
andrey@debian:~$ cat /proc/acpi/thermal_zone/THRM/temperature 
temperature:             104 C
andrey@debian:~$


фшоке. надо срочно ноут разбирать и пылюку выгребать. Да и завал бумаг не мешает разгрести. Еще и отопление включили :shock:
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

Re: blindman - [ПЛИС - с чего начать?]

Сообщение blindman » 30 дек 2011, 05:38

Есть такая задача: принимать данные по SPI, записывать в кольцевой буфер. При заполнении буфера до определенного порога - выдать сигнал, чтобы передатчик притормозил. Содержимое буфера надо выдавать на другие ноги, тоже через последовательный интерфейс, он должен синхронизироваться с внешним тактовым сигналом, частота которого может меняться. Суть в том, чтобы обеспечить на выходе стабильный поток данных, синхронизированный с внешним тактом, независимо от скорости поступления данных на вход (в разумных пределах). Скорости вывода - до 6200 кбит/с. Принимать на большей скорости (до 20 МБит/с)


С ПЛИСами никогда не работал. Имеется в наличии EPM3064ALC44-10. Ног вроде хватает впритык для интерфейсов и подключения ОЗУ на 32 кБ. Хватит ли ее для такой задачи? Что можно почитать про работу с ПЛИС для начала?
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

Пред.След.

Вернуться в Блоги

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 0

cron