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

avr123.nm.ru

Странно как-то. 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

blindman

Ага. Bus-powered - это когда от USB берется питание и через стабилизатор на VDD подается

Michael_K

Там, мне казалось, стабилизатор встроенный, но, конечно, это предусмотреть на плате надо...
А не вариант что-нить в районе 6-7 ноги отрезать-коротнуть?

blindman

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

dccharacter

Писал же! forum14/topic9235.html

blindman

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

=DeaD=

Конечно существует. Только задачу надо избавить от 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 секунды:
Ну а реализация в софте - либо динпрог, либо перебор, тут уж смотря какие требования к производительности и наличию времени на кодинг.

boez

=DeaD= писал(а):

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

Это я так понимаю, если народ умными словами не пугать, просто рекурсия - из функции R(z) вызываем R(2^(n+1)-z) и R(z-2^n) и смотрим, какое решение оптимальнее? Ну а R(0) и R(+-1) возвращают константные решения, так?

blindman

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

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

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

В дополнение - если m - минимальное неотрицательное целое, такое что |k| < 2^m, количество элементов решения не превышает (m >> 1) + 1

Michael_K

blindman писал(а):

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

=DeaD= писал(а):

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

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

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

То есть делаем не четыре сдвига и четыре сложения, а три сдвига и три сложения, но используем лишнюю ячейку памяти для промежуточного результата.
Ну и с минусами так же - просто примеры не столь очевидные.

=DeaD=

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

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:

Michael_K

такие формулы я не понимаю - это для меня слишком сложно

и лениво...
может быть проще на множители раскладывать... только вот не всегда оптимум получится. Его нужно как-то отдельно оценивать... И правда перебором что-ли...

=DeaD=

А R(q)*R(z/q) это и есть раскладывание на множители

blindman

Код:

andrey@debian:~$ cat /proc/acpi/thermal_zone/THRM/temperature 
temperature:             104 C
andrey@debian:~$ 

фшоке. надо срочно ноут разбирать и пылюку выгребать. Да и завал бумаг не мешает разгрести. Еще и отопление включили :shock:

blindman

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

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

roboforum.ru

Правила форума

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

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