A COMBINATORIAL PROBLEM RELATED TO DYNAMIC MEMORY STRUCTURES
Original Publication Date: 1975-Oct-14
Included in the Prior Art Database: 2007-Mar-30
Software Patent Institute
Wong, C.K.: AUTHOR [+2]
RC 5678 (iI24441) 1 0 1 4 7 5 Computer
A COMBINATORIAL PROBUM RELATED TO DYNAMIC MEMORY STRUCTURES
IBM Thomas 3. Wat'son Research Center
Yorktown Heights, New York 10598
Typed by Joan Petrosi1:Lo on MTST
ABSTRACT: In this paper we consider a combinatorial problem
arising from a study in computer memory structures. Given a
sequence x of 0,1,-1, two functions R(x), A(x) are defined.
Their maximum and average values over a set of sequences are
computed and the choice of the value of a parameter to
minimize these values is discussed.
(iI24441) 1 0 / 1 4 / 7 5 Computer
1,IIlITED DISTRIBUTION NOTICE
This report has been submitted for publication elsewhere and has been issued as a Kesearch Keport for early dissemination of its contents. '4s a courtesy to the intended publisher, it should not be widely distributed until after the date of outside publication.
Copies may be requested from:
IB.11 Thomas J. R'atson Research Center Post Office Box 318
Yorktown Heights, New York I0598
I. STATEMENT OF THE PROBLEM
In a study of access t i m e in various computer memory structures [l],
the following combinatorial problem comes up. Before describing it in de- tails, we need the following definitions.
Definition 1. Let k = cd, when c, d are positive integers. Let x be a sequence of k digits, a digit being either 0,1, or -1. Divide x into c blocks of d digits each. Number the blocks 1,2, ..., c from right to left. d-1
Suppose the digits in a block are a d-lt. . t al I a. - Then a = C a. 2l is
said t o be the number represented by the block. Let the number represented by block i be a i = 1 , 2 , . . c . If a , f 0 for some i > 1, l e t q
i ' L
be the smallest index such that q > 1 and a # 0. q
0 i f a = 0 for a l l i > 1 i
Define R(x) =
C c-q + 1 otherwise.
Definition 2. Given an integer x 2 0, the signed-digit representation of x is defined as follows:
(i) First represent x as a binary number, say, an-l...al ao, where a is 0 or 1. Suppose a = aj+l - . . .=a = 1 and the positions i j j+t-1
j-1 and j+t are either empty or containing 0's only. Then the sequence a j+t-l.. . a a is called a string of 1's with length t.
(ii) Scan the binary representation of x from right to left. Let x = a ...
a be the f i r s t string of 1's with length t > 2. Replace x 1 j+t-1 j - 1
by the sequence x' = 1 0 0. ..0-1, where the digit -1 occupies the position
originally occupied by a and t-1 zeros are between the digits 1 and -1.
(1 is therefore a carry and occupies the position j+t).
(iii) Scan the new representation from right to left starting with position j+t, and repeat the process in (ii).
The resulting sequence of digits 0,1,-1 is defined as...