Browse Prior Art Database

A COMBINATORIAL PROBLEM RELATED TO DYNAMIC MEMORY STRUCTURES

IP.com Disclosure Number: IPCOM000148687D
Original Publication Date: 1975-Oct-14
Included in the Prior Art Database: 2007-Mar-30

Publishing Venue

Software Patent Institute

Related People

Wong, C.K.: AUTHOR [+2]

Abstract

RC 5678 (iI24441) 1 0 1 4 7 5 Computer Science A COMBINATORIAL PROBUM RELATED TO DYNAMIC MEMORY STRUCTURES IBM Thomas 3. Wat'son Research Center Yorktown Heights, New York 10598 Mathematics Typed by Joan Petrosi1:Lo on MTST 23 pages 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. 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 318Yorktown Heights, New York I0598

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 15% of the total text.

Page 1 of 30

A COMBINATORIAL PROBUM RELATED TO DYNAMIC MEMORY STRUCTURES

IBM Thomas 3. Wat'son Research Center
Yorktown Heights, New York 10598
Mathematics

                 Typed by Joan Petrosi1:Lo on MTST
23 pages

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.

RC 5678

(iI24441) 1 0 / 1 4 / 7 5 Computer

Science

[This page contains 1 picture or other non-text object]

Page 2 of 30

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

[This page contains 1 picture or other non-text object]

Page 3 of 30

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
1

i=

0

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.
j+l j
(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

[This page contains 1 picture or other non-text object]

Page 4 of 30

by the sequence x' = 1 0 0. ..0-1, where the digit -1 occupies the position
1

originally occupied by a and t-1 zeros are between the digits 1 and -1.
j

(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...