*Помогите найти объем памяти

mOleg

Подарили мне микросхему памяти, да не простую а с данными случаными, только забыли сообщить, каков у нее объем, а узнать, сколько же места в ней хочется. Чтение из нее последовательное, можно за раз только один бить прочесть, и перебирать адреса в ней можно только по одному биту (либо бит влево, либо бит вправо), соответсвенно читать и писать можно, но только в текущее положение. Помогите достоверно определить, сколько же памяти мне подарили.

: сколькобит ( --> # ) 
                    ;

так как микросхему подарили только мне, то проверить алгоритм можно только с помощью следующего кода-симулятора:

TIMER@ D>S 137 MOD ABS BEGIN RANDOM DROP *WHILE 1 - REPEAT DROP
0x1000 CHOOSE 1 MAX CONSTANT объем

объем BLOCK VALUE память
0 VALUE адрес

: текущий ( --> addr ) адрес память + ;

: влево  ( --> ) адрес 1 - [ объем 1 - ] LITERAL UMIN TO адрес ;
: вправо ( --> ) адрес 1 + объем UMOD TO адрес ;
: прочесть ( --> flag ) текущий B@ 0 <> ;
: изменить ( --> ) прочесть -1 XOR текущий B! ;
\ инициализация массива
объем BEGIN *WHILE  RANDOM 1 AND IF изменить THEN вправо  1 - REPEAT DROP
\ случайный адрес
объем CHOOSE TO адрес

вместо xxx подставить случайные числа, массив проинициализировать случайным содержимым. Размер любой в диапазоне от одной ячейки до 1 Гигабита. Обратите внимание на то, что адресация закольцована, т.е. перейдя последний бит попадаем в первый, и наоборот.

*поправил код симулятора памяти

вопрос

если диапазон до 1 гигабита, обнуляем более 1 гигабита и затем устанавливаем единственную единичную ячейку - бит и затем движемся по кругу :ищем её, длина пути поиска и будет объём памяти :?:

"не простую а с данными случаными"

WingLion

А считать всю память реально?

1. N=0

2. Читаем 2^N бит, запоминаем,
3. читаем следующие 2^N бит, тоже запоминаем, сравниваем с первыми 2^N бит.
4. Если не совпадают, увеличиваем N на 1 и возвращаемся к п.3
Если первые 2^N бит совпадают со вторыми 2^N, N становится кандидатом на
количество адресов памяти.
5. Читаем все остальное до предполагаемого предела - 1Гбита, проверяя, что все остальные данные повторяются. Если появляются неповторяющиеся данные - увеличивать N на единицу и снова на п.3.
Если есть подозрения, что память больше 1Гбит, повторять до нового предполагаемого предела.

Если информацию в памяти сохранять не надо, Проверить можно и так:
1. Пишем с начала последовательные двоичные числа разрядности скажем 256, начиная с нуля затем пробегаем 2^N бит вперед, пишем дальше следующее число, возвращаемся назад na 2^N бит и проверяем, что там оказалось. Если нуль, увеличиваем N на 1 и пишем дальше числа, возвращаясь назад каждый раз, когда адрес достигает степени двойки, пока первый ноль не окажется затерт.

p.s. первый вариант алгоритма когда-то использовал для проверки объема прошитых ПЗУ-шек, вставляемых в программатор.

mOleg

WingLion писал(а):

2. Читаем 2^N бит, запоминаем,

и, вот, скажем размер 1 бит

WingLion писал(а):

3. читаем следующие 2^N бит, тоже запоминаем, сравниваем с первыми 2^N бит.

WingLion писал(а):

а там случайно, скажем значение "101010101010101010", или другое регулярное

WingLion писал(а):

4. Если не совпадают, увеличиваем N на 1 и возвращаемся к п.3Если первые 2^N бит совпадают со вторыми 2^N, N становится кандидатом на количество адресов памяти.

скажем, размер памяти - простое число

WingLion

Код:

: вперед вправо ; 
: назад влево ;

: записать-0 прочесть IF изменить THEN ;
: записать-1 записать-0 изменить ;

: вперед-NN  0 DO вперед LOOP ;
: назад-NN 0 DO назад LOOP ;

0 VALUE NN

: тест-NN ( NN --> )
   1 TO NN  записать-0
   BEGIN
   NN вперед-NN
   записать-1
   NN назад-NN  прочесть IF EXIT THEN
   NN вперед-NN записать-0 
   NN назад-NN 
   NN 1 + TO NN
   AGAIN
;

: сколькобит тест-NN NN ;

вилами по воде не проверено(!)

mOleg

решение WingLion не верно, прошу исправить (должно хотя бы компилироваться и соответсвтовать условию задачи, а, желательно, и работать).

WingLion писал(а):

вилами по воде не проверено(!)

нет смысла выкладывать заведомо нерабочие решения, т.к. сюда смотрят новички!!!

Двум персонажам вынес предупреждение по пункту 6 правил данного раздела,
мусорные сообщения вынес в отдельный топик.

chu

Код:

  : сколькобит ( -- u )

        0  записать-0
        begin 1+
            dup вперед-NN записать-1
            dup  назад-NN прочесть
        until
        ;

если на микросхеме есть маркировка, то можно погуглить даташит

mOleg

Самое простое и медленное решение
(использован fork)
Кто придумает быстрее?

source file: ramsize.fts
\ 15.06.2012

  math/   mersenne.fts
  os/     heap.fts
  util/   timer.fts
  branch/ for-next.fts

CONTAINER сокрыто

TIMER@ D>S 137 MOD ABS BEGIN RANDOM DROP *WHILE 1 - REPEAT DROP
0x1000 CHOOSE 1 MAX CONSTANT объем

объем BLOCK VALUE память
0 VALUE адрес

: текущий ( --> addr ) адрес память + ;

RECENT ALSO сокрыто

: влево  ( --> ) адрес 1 - [ объем 1 - ] LITERAL UMIN TO адрес ;
: вправо ( --> ) адрес 1 + объем UMOD TO адрес ;
: прочесть ( --> flag ) текущий B@ 0 <> ;
: изменить ( --> ) прочесть -1 XOR текущий B! ;

\ инициализация массива
объем BEGIN *WHILE  RANDOM 1 AND IF изменить THEN вправо  1 - REPEAT DROP
\ случайный адрес
объем CHOOSE TO адрес

: проверить s" сколькобит" SFIND IF EXECUTE THEN
            DUP ." посчитано: \t" .
                ." \n\rисходный объем: " объем DUP .
            = IF    ." \n\r решение верно."
               ELSE ." \n\r решение не верно."
              THEN ;

PREVIOUS

\ сместиться влево на указанное число бит
: Левее  ( # --> ) FOR влево TILL ;

\ сместиться вправо на указанное число бит
: Правее ( # --> ) FOR вправо TILL ;

\ проверить следующий бит
: следущий? ( # --> bit ) DUP Правее изменить  Левее прочесть ;

\ определить объем памяти
: сколькобит ( --> # )
                 1 >L \ счетчик размера
             прочесть IFNOT изменить THEN
             BEGIN L@ следущий? WHILE 1 L+ REPEAT
                   L> ;

проверить

mOleg

более быстое решение (опять fork)

source file: ramsize1.fts
\ 17.06.2012 m0leg

  math/   mersenne.fts
  os/     heap.fts
  util/   timer.fts
  branch/ for-next.fts

CONTAINER сокрыто

TIMER@ D>S 137 MOD ABS BEGIN RANDOM DROP *WHILE 1 - REPEAT DROP
0x1000 CHOOSE 1 MAX CONSTANT объем

объем BLOCK VALUE память
0 VALUE адрес

: текущий ( --> addr ) адрес память + ;

RECENT ALSO сокрыто

: влево  ( --> ) адрес 1 - [ объем 1 - ] LITERAL UMIN TO адрес ;
: вправо ( --> ) адрес 1 + объем UMOD TO адрес ;
: прочесть ( --> flag ) текущий B@ 0 <> ;
: изменить ( --> ) прочесть -1 XOR текущий B! ;

\ инициализация массива
объем BEGIN *WHILE  RANDOM 1 AND IF изменить THEN вправо  1 - REPEAT DROP
\ случайный адрес
объем CHOOSE TO адрес

: проверить s" сколькобит" SFIND IF EXECUTE THEN
            DUP ." посчитано: \t" .
                ." \n\rисходный объем: " объем DUP .
            = IF    ." \n\r решение верно."
               ELSE ." \n\r решение не верно."
              THEN ;

PREVIOUS

\ сместиться влево на указанное число бит
: Левее  ( # --> ) FOR влево TILL ;

\ сместиться вправо на указанное число бит
: Правее ( # --> ) FOR вправо TILL ;

\
: проверка  ( bit # --> bit # flag )
            изменить
            DUP Левее
            OVER прочесть <>
            IF FALSE ;THEN
            DUP Правее TRUE ;

\ проверить следующий бит
: следущий? ( bit # --> bit flag )
            OVER прочесть =
            IF проверка
             ELSE TRUE
            THEN ;

\ определить объем памяти
: сколькобит ( --> # )
             прочесть 1
             BEGIN вправо
                   следущий? WHILE
                1 +
             REPEAT NIP ;

проверить

*Помогите найти объем памяти

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