FORM 2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENTS RULES, 2003
COMPLETE SPECIFICATION
(See section 10, rule 13)
1. Title of the invention: DATA PROCESSING BASED ON MULTI-BASE NUMBERS
2. Applicant(s)
NAME NATIONALITY ADDRESS
TATA CONSULTANCY Indian Nirmal Building, 9th Floor, Nariman Point,
PERVICES LIM1TED Mumbai 400021, Maharashtra, india
3. Preamble to the description
COMPLETE SPECIFICATION
The following specification particularly describes the invention and the manner in which it
is to be performed.

TECHNICAL FIELD
The present subject matter, in general, relates to data processing and, in particular,
to data processing based on multi-base numbers.
BACKGROUND
Real-time applications, such as digital signal processing and security applications,
may be computationally complex as they require processing large data. Typically, the processors are configured to process data, such as numerical data, in the form of bits.
Numerical data is generally represented using various number systems. The
number systems provide a unique representation to every number and an algebraic structure for the numbers. Traditional Single-Base Number Systems (SBNS), such as binary, octal, decimal, and hexadecimal systems, include one base only, for example, the base is 2 for binary numbers, 8 for octal numbers, 10 for decimal numbers, and 16 for hexadecimal numbers.
In recent years, Double-Base Number System (DBNS) and Multi-Base Number
System (MBNS) have been introduced for various applications which generally involve large numbers and complex calculations. The DBNS takes two bases, whereas the MBNS takes more than two bases to represent a number. Generally, first few prime numbers (2, 3, 5, 7....and so on) can be chosen as the bases for the DBNS and the MBNS. A typical DBNS representation for integer 127 can be 2233 + 2!32 + 2°3° or 2233 + 243° + 2°3l or 253] + 2°33 + 223°. Similarly, a typical Triple-Base Number System (TBNS) representation, which is a type of MBNS representation, for the integer 127 can be 2°3°53 +2'3°50 or22335°+ 21325°+ 2°305°.
Clearly, these representations are highly redundant as one integer can have
multiple MBNS representations. The MBNS representations with the minimum number of sets of n-integers (2a3b 5c. nx) are called optimum MBNS representations as they consume fewer bits. Finding the optimum MBNS representation from various possible MBNS representations may be a time and resource consuming process, for example, integer 127 can have multiple TBNS representations, among which only one is optimum representation, i.e., 2°3°53 + 213°5o having only two 3-integers.
Many theoretical approaches have been proposed for representing a number into
the MBNS representations. One of such approaches involves using lookup tables with a specific

addressing scheme. In real-time applications, such as digital signal processing and security applications, such lookup tables based solutions become unrealistic to implement because the real-time applications generally involve large numbers and complex calculations.
SUMMARY
This summary is provided to introduce concepts related to data processing based
on multi-base numbers. These concepts are further described below in the detailed description. This summary is not intended to identify essential features of the claimed subject matter nor is it intended for use in determining or limiting the scope of the claimed subject matter.
The method includes computing a first n-integer which is largest of integers less
than or equal to an input data. Further, exponents corresponding to the first n-integer are stored in a memory. Further, a first difference between the input data and the first n-integer is ascertained. A maximum value for an exponent of each base of a next n-integer is determined as a minimum of a stored exponent of corresponding base and one plus floor of logarithm of the first difference in the corresponding base. The method further includes computing the next n-integer nearest to the first difference with exponents in a range of zero to the maximum value of the corresponding base.
BRIEF DESCRIPTION OF THE DRAWINGS
The detailed description is provided with reference to the accompanying figures.
In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. The same numbers are used throughout the drawings to reference like features and components.
Fig. 1 illustrates components of a data processing system, in accordance with an
implementation of the present subject matter.
Fig. 2 illustrates a method for processing data, in accordance with an
implementation of the present subject matter.
DETAILED DESCRIPTION
The present subject matter relates to methods and systems for data processing
based on multi-base numbers.

In recent years, the Multi-Base Number System (MBNS) has proved to be
efficient in applications involving large numbers and complex calculations, such as digital signal processing (DSP), data security, and data compression. The efficiency of the MBNS is due to the fact that a MBNS representation generally utilizes fewer bits as compared to a traditional Single-Base Number System (SBNS) representation of a number or even a Double-Base Number System (DBNS) representation. Thus, processing systems could be preferred for certain complex operations.
In addition, the MBNS has proved to be efficient in executing arithmetic
operations, such as addition, subtraction, and multiplication. Efficiency in executing the arithmetic operations allows the MBNS to be useful for effectively solving mathematical problems, particularly in real-time applications, such as digital signal processing (DSP), data security, and data compression. The arithmetic operations are generally executed by processors provided in various devices running the real-time applications. For example, processors provided in a filter bank of a cellular communication device may be configured to perform the arithmetic operations. However, the processors based on the MBNS generally have high hardware complexity and increased latency in cases of large bit size data.
Recent advances in the DSP require processors capable of high speed processing
of signal data in real-time with a high degree of adaptability. In addition, minimization of energy consumption and chip area are desired for increasing efficiency of the processors required for the real-time applications, such as DSP. Further, the processors execute arithmetic operations, such as multiplication and addition, thus major design requirements relate to enhancement of the processor's capability to execute the arithmetic operations. Additionally, executing the arithmetic operations include, apart from processing numbers, converting the numbers from their standard representation to the MBNS representation before being processed and converting back to the standard representation after being processed, thus increasing the computation time and complexity.
In an implementation, according to the present subject matter, systems and
methods for data processing based on multi-base numbers are described. In one example, the method for data processing may be implemented in a hardware device, such as processors; a data processing program running on a computing system; or a combination thereof. For example, the

method for data processing may be implemented on a computing system for computing elliptic curve cryptography (ECC) scalar multiplication, whereas for filter bank designs in mobile handsets and hearing aids. The method for data processing may be implemented using various hardware components, such as adders, shifters, sign correctors, and generators.
In one implementation, the input data is received by a data processing system for
processing. The input data, say an integer, is then converted from its standard representation to the MBNS representation in the form Σ2a3b5c...nx, i.e., as a sum of one or more n-integers of the form 2a3b5c...nx. where n is a prime number. Generally, first few prime numbers can be chosen as bases of the MBNS representation. For example, prime numbers 2, 3, and 5 can be chosen as the bases for Triple-Base Number System, similarly 2, 3, 5, and 7 can be chosen as the bases for Quadruple-Base Number System.
In an implementation, a first n-integer which is largest of n-integers less than or
equal to an input data is computed and an exponent of each base of the first n-integer is stored in a memory, such as a stack memory. For example, a first 3-integer less than or equal to the input data 97 is say 213251. i.e., 90, and exponents {121} of the first 3-integer 213251, i.e., 90, are stored in the memory. Further, a first difference between the input data and the first n-integer is ascertained. In the above mentioned example, the first difference between the input data 97 and the first 3-integer 213251, i.e., 90 is 7.
In said implementation, if the first difference is non-zero, then a maximum value
for exponent of each base of a next n-integer of the MBNS representation is determined. The maximum value is defined by a minimum of a stored exponent of corresponding base and one plus floor of logarithm (log) of the first difference in the corresponding base. In mathematics and computer science, the floor function maps a real number the largest integer not greater than the real number. In the above mentioned example, the first difference is 7 and thus non-zero. Accordingly, the maximum value for exponents of next 3-integer is defined as:
Maximum value of a(n) = min {(a(n-l), 1 + Floor [Log2 (first difference)]}
Maximum value of b(n) = min {(b(n-l), 1 + Floor [Log3 (first difference)]}
Maximum value of c(n) = min {(c(n-l), 1 + Floor [Logs (first difference)]}

Here. a(n), b (n), and c(n) are exponents of base 2, base 3, and base 5 respectively, of the next 3-integer and are defined by the stored values {121 }and the first difference 7 as indicated below:
Maximum value of a(n) = min {1,1+ Floor [Log2 7]} = min {1, 3} = 1
Maximum value of b(n)= min {2, 1 + Floor [Log37]} = min {2, 2} = 2
Maximum value of c(n) = min {1,1+ Floor [Log57)]} = min {1, 2} = 1
In said implementation, if the first difference is non-zero, then the next n-integer
nearest to the first difference is computed with exponents in a range of zero to the maximum value of the corresponding base. In the above mentioned example, the next n-integer nearest to the first difference of 7 is 2l3l50, i.e., 6 with exponents in range of 0 to 1, 0 to 2, and 0 to 1. The exponents of the next n-integer are stored in the memory, such as the previously discussed stack memory. In the above mentioned example, exponents {110} of the next 3-integer 2 3 5 nearest to the difference of 7 are stored in the memory.
Further, a next difference between the first difference and the next n-integer is
ascertained. In the above mentioned example, the next difference is 1 between the first difference 7 and the next n-integer 2 13150, i.e., 6. Now if the next difference is non-zero, then this next difference becomes the first difference to create a loop that keeps on computing the next n-integers till the next difference becomes zero. In the above mentioned example, the next difference of 1 becomes the first difference and the next 3-integer corresponding to 1 is computed which is 2°3°5° based on determined maximum values. Like the previous exponents, exponents {000} are also stored in the stack memory. In the end, the MBNS representation of the input data can be obtained from the stack memory. In the above mentioned example, the MBNS representation for the input data 97 as obtained from the stack memory is {121} {110} {000}. As can be observed, in the above mentioned example, the systems and methods, according to the present subject matter, generate multi-base numbers with a decreasing order of exponents, which are useful in applications like Elliptic Curve Cryptography (ECC) scalar multiplication, Very-large-scale integration (VLSI) design. Inner-product computation unit, Mobile hardware platforms, etc.
With reduction in bits required to represent numbers, the systems and methods,
according to the present subject matter, can be utilized for encoding and decoding in data

compression techniques to compress data into a smaller size and thus achieve a high compression ratio.
The systems and methods, according to the present subject matter, can also be
utilized to design MBNS based processors that can be 8 times smaller than equivalent binary processors. As a result, power consumption can be reduced by at least 50% as compared to binary processors. In one implementation, the power consumption can be reduced by at least 66% as compared to the binary processors. The DBNS based processors can be utilized to improve the performance of filter-bank design in mobile handsets, hearing aid instruments and other simiJar tiny devices where chip area is a major design consideration.
In applications, such as linear and non-linear filtering and elliptic curve
cryptography (ECC) scalar multiplication, the systems and methods, according to the present subject matter, help in reducing the complexity and time involved in executing the arithmetic operations as the processors now need to execute the arithmetic operations using less number of bits. For example, for multiplying two numbers represented in the form of the TBNS, say 2a3b5c and 2d3e5f, the processors simply need to add exponents corresponding to a common base. In the above example, the processor needs to add sa: with 'd', 'b' with 'e', and 'c' with T to compute the multiplication as 2a+d3b+e5c+f. Similarly, for dividing two numbers represented in the form of the TBNS, the processors simply need to subtract exponents corresponding to the common base.
Although aspects of the systems and methods for data processing based on multi-
base numbers have been described using examples of triple-base numbers, it is to be understood that the invention is not necessarily limited to triple-base numbers. The invention according the present subject matter can be easily implemented for any multi-base numbers, such as quadruple-base numbers and quintuple-base numbers.
While aspects of systems and methods for data processing based on multi-base
numbers can be implemented in any number of different computing systems, environments, and/or configurations, the implementations are described in the context of the following exemplary system architecture(s).
Fig. 1 illustrates data processing system 100 in accordance with an
implementation of the present subject matter. Examples of the data processing system 100 include, but are not limited to, computing devices such as mainframe computers, workstations,

personal computers, desktop computers, minicomputers, servers, multiprocessor systems, and laptops; cellular communicating devices such as personal digital assistants, smart phones, and mobile phones; DSP based devices, such as hearing aid devices; and the like.
The data processing system 100, hereinafter referred to as the system 100,
includes one or more processor(s) 102, I/O interface(s) 104, and a memory 106 coupled to the processor 102. The processor 102 can be a single processing unit or a number of processing units, all of which could also include multiple computing units. The processor 102 may be implemented as one or more microprocessors, microcomputers, microcontrollers, digital signal processors, central processing units, state machines, logic circuitries, and/or any devices that manipulate signals based on operational instructions. Among other capabilities, the processor 102 is configured to fetch and execute computer-readable instructions and data stored in the memory 106.
Functions of the various elements shown in the figures, including any functional
blocks labeled as "processor(s)", may be provided through the use of dedicated hardware as well as hardware capable of executing software in association with appropriate software. When provided by a processor, the functions may be provided by a single dedicated processor, by a single shared processor, or by a plurality of individual processors, some of which may be shared. Moreover, explicit use of the term "processor" should not be construed to refer exclusively to hardware capable of executing software, and may implicitly include, without limitation, digital signal processor (DSP) hardware, network processor, application specific integrated circuit (ASIC), field programmable gate array (FPGA), read only memory (ROM) for storing software, random access memory (RAM), and non volatile storage. Other hardware, conventional and/or custom, may also be included. Further, the processor 102 may include various hardware components, such as adders, shifters, sign correctors, and generators required for executing various applications such as arithmetic operations.
The I/O interface(s) 104 may include a variety of software and hardware
interfaces, for example, interface for peripheral device(s), such as a keyboard, a mouse, an external memory, and a printer. Further, the I/O interface(s) 104 may enable the system 100 to communicate with other computing devices, such as a personal computer, a laptop, and the like.

The memory 106 may include any computer-readable medium known in the art
including, for example, volatile memory such as static random access memory (SRAM) and dynamic random access memory (DRAM), and/or non-volatile memory, such as read only memory (ROM), erasable programmable ROM. flash memories, hard disks, optical disks, and magnetic tapes. The memory 106 also includes modules 108 and data 110.
The modules 108 include routines, programs, objects, components, data
structures, etc., which perform particular tasks or implement particular abstract data types. The modules 108 further include a first n-integer module 112, a first difference module 114, a maximum value module 116, a next n-integer module 118, a next difference module 120, and other module(s) 122. The other module(s) 122 may include programs or coded instructions that supplement applications and functions of the system 100.
On the other hand, the data 110, amongst other things, serves as a repository for
storing data processed, received, and generated by one or more of the modules 108. The data 110 includes, for example, input data 124, first n-integer data 126, first difference data 128, maximum value data 130, next n-integer data 132, next difference data 134, exponents data 136, and other data 138. The other data 138 includes data generated as a result of the execution of one or more modules in the other module(s) 122.
In one implementation, the system 100 receives the input data. The input data, for
example, in form of a number or combination of numbers, could represent any type of data, such as audio-video data and document data. The system 100, in one example, is configured to process data required in various real-time applications like data security, digital signal processing (DSP), data compression, etc. The system 100 is further configured to provide data based on the MBNS representation to be utilized in the real time applications.
In one implementation, the system 100 may be a cryptography system configured
to process input data, such as a private key or a public key represented in the form of numbers, to obtain cryptographic data such as digital signatures based on the MBNS representation. Using the MBNS representation, in the cryptography system, reduces computational time and resources as the MBNS representation utilizes fewer bits to represent data.
In one implementation, the system 100 may be a mobile phone and the processor
102 may be configured to implement a signal processing filter for processing voice data based on

the MBNS representation. Using the MBNS representation, in the mobile phones improves its efficiency and response time as the MBNS representation utilizes fewer bits to represent data.
In one implementation, the system 100 may be a system of ECC scalar
multiplication configured to compute an integer multiple of an element in additive group on an elliptic curve, i.e., to compute K*P for any integer K and a point P on the elliptic curve. Using the MBNS representation for ECC scalar multiplication reduces computational complexity involved therein.
In one example, an integer is an n-integer if all of its prime divisors are among the
first n prime numbers, such as 2, 3, 5,..., and so on. The n-integer is represented as 2a3b5c..,,nx and is a single summand of a typical MBNS representation given below:

The system 100 processes the input data to provide a MBNS representation in the
form as a sum of one or more n-integer s of the form 2a3 5C.. ,nx.
The first n-integer module 112 receives the input data. In one implementation, the
first n-integer module 112 stores the input data in the input data 124. Further, the first n-integer module 112 computes the first n-integer which is largest of n-integers less than or equal to the input data. For example, if an integer 85 is received as the input data, then the first 3-integer which is largest of n-integers less than or equal to 85 can be 2°345°, i.e.. 81. In one implementation, the first n-integer module 112 stores the first n-integer in the first n-integer data 126.
Since the first n-integer serves as a first n-integer of the MBNS representation,
therefore, keeping the first n-integer less than or equal to the input data helps in decreasing the memory consumption in small processors. Further, in processors, such as a 64 bit processor, computing the first 3-integer less than the input data will consume less memory as compared to memory consumed by the first n-integer greater than the input data. For example, a 63-bit integer n = 9223372036854775806 may be expressed as a difference of a 64-bit number (9223372036854775808) and 2, i.e., 9223372036854775808 - 2 = 263 -2. Computing such a representation that exceeds 64 bit computation requires the use of a multi-precision integer arithmetic (MIA) library. However, using the MIA library for computations consumes more

memory and power, which may not suitable for tiny hardware processors, such as processors used in hearing aids. Thus, the first n-integer is always computed as a largest n-integer less than or equal to the input data.
In one implementation, the first n-integer module 112 is configured to store values
of exponents (al, bl, cl...xl) corresponding to the first n-integer in the exponents data 136. For example, if the first n-integer module 112 computes the first 3-integer as 2°345°, i.e., 81, then the exponents {040} are stored in the memory 106, for example, in the exponents data 136.
Upon computation of the first n-integer, the first difference module 114 ascertains
the first difference between the input data and the first n-integer. In one implementation, the first difference module 114 subtracts the first n-integer from the input data in order to obtain the first difference. For example, the first difference module 114 ascertains a first difference between the input data, say 85, and the first 3-integer 2°345°, i.e., 81 as 4. In one implementation, the first difference module 114 stores the first difference in the first difference data 128.
When the first difference is non-zero, then the maximum value module 116
determines the maximum value for an exponent of each base of the next n-integer of the MBNS representation. In one implementation, the maximum value module 116 stores the maximum value in the maximum value data 130. In one implementation, the mYmllm value is defined by a minimum of a stored exponent of corresponding base and one plus floor of log of the first difference in the corresponding base. For example, the maximum values for exponents of the next 3-integer are defined as:
Maximum value of a(n) = min {(a(n-l), 1 + Floor [Log2 (first difference)]}
Maximum value of b(n) = min {(b(n-l), 1 + Floor [Log3 (first difference)]}
Maximum value of c(n) = min {(c(n-l), 1 + Floor [Logs (first difference)]}
Here, a(n). b (n), and c(n) are exponents of base 2, base 3, and base 5 respectively of the next 3-integer. In the above mentioned example, the maximum values of exponents corresponding to the next 3-integer are defined by the stored values {040} and the first difference of 4 as indicated below:
Maximum value of a(n) = min {0, 1 + Floor [Log24]} = min {0,3} = 0
Maximum value of b(n) = min {4. 1 + Floor [Log34]} = min {4, 2} = 2

Maximum value of c(n) = min {0, 1 + Floor [Logs4]} = min {0, 1} = 0
When the first difference is non-zero, then the next n-integer module 118
computes the next n-integer nearest to the first difference with exponents in a range of zero to the maximum value of the corresponding base as provided by the maximum value module 116. Jn the above mentioned example, the next 3-integer nearest to the first difference of 4 is 2 3 5 , i.e., 3 with exponents in range of 0 to 0, 0 to 2, and 0 to 0. In one implementation, the next n-integer module 118 stores the next n-integer in the next n-integer data 132. In one implementation, the next n-integer module 118 stores exponent of each base of the next 3-integer in the exponents data 136. In the above mentioned example, exponents {010} of the next 3-integer 2°315° nearest to the first difference of 4 are stored in the exponents data 136. In one implementation, the next n-integer module 118 may compute the next n-integer based on predefined computation rules such as computing n-integers which are non-repeating, i.e., a set of already stored exponents is not repeated in the MBNS representation of the input data.
Further, the next difference module 120 ascertains the next difference between the
first difference and the next n-integer. In the above mentioned example, the next difference between the first difference 4 and the next 3-integer 203150, i.e., 3 is 1. In one implementation, the next difference module 120 stores the next difference in the next difference data 134. When the next difference is non-zero, the next difference can be taken as the first difference for computing the next 3-integer. The cycle is repeated again with the next difference taken as the first difference. In the above mentioned example, 1 is assigned as the first difference to create a loop that keeps on computing the next-n integers till the next difference becomes zero. In this way, the MBNS representation with decreasing order of exponents for input data 85 is 2°345° + 203150+203050, i.e., 81+3+1.
Consider another example, where input data is say 97 and the first 3-integer which
is largest of n-integers less than or equal to 97 is say 21325l, i.e., 90. The exponents {121} are stored in a memory. The first difference is ascertained as 7. Further, based on first difference of 7 and exponents {121}, maximum values for exponents of the next 3-integer are determined as {1,2,1}. The next 3-integer is 21315°, i.e., 6 with exponents in the range {0-1, 0-2, 0-1}. The exponents {110} are stored in the exponents data 136. In this example, the next difference between 7 and 6 is 1. Since the next difference is non-zero, it is assigned to the maximum value

module 116 and the next n-integer module 118 as the first difference. The maximum value module 116 then determines, based on the next difference of 1 and stored exponents {110}, maximum values for representation of 1 as {111}. Based on the maximum value, the next n-integer module 118 computes the next 3-integer nearest to 1 as 203050. Like the previous exponents, exponents {000} are also stored in the exponents data 136. The MBNS representation of the input data is obtained from the memory. In the above mentioned example, the MBNS representation obtained from the memory 106 for input data 91 is 213251 + 213150 + 203050, i.e., {121}{110}{000}. As can be observed, in the above mentioned example, the systems and methods, according to the present subject matter, generate multi-base numbers with a decreasing order of exponents, which are useful in applications like ECC scalar multiplication. Very-large-scale integration (VLSI) design, Inner-product computation unit, Mobile hardware platforms, etc.
In an implementation, the MBNS representation can be in the form
(2al3bt5c,...nxl) +(2a23b25c2 ...n*2) ±...(2an3bn5cn...nxn). In such a case, sign data (not shown) may be used to keep track of the sign of an n-integer (2a3b5c ...nx) of the MBNS representation. For this purpose, the processor 102 may include a sign corrector (not shown) or the system 100 may include a sign correction module (not shown) in the memory 106.
In one implementation, the next n-integer can be greater than the first difference.
Consider an example: where input data is say 98; the first 3-integer is 2 3 5 . i.e., 90; and accordingly maximum allowed exponents for next 3-integer are {121}. In this example, the first difference of 8 can be represented as 9-1 and thus the next 3-integer is 2°325°, i.e., 9 which is greater than the first difference 8. In the end, input data 98 can be represented as 213251 + 2°325° -2°3050,i.e.,90 + 9-L
In one implementation, the sign data may be stored along with the exponents. For
instance in the example given below, negative sign of the 3-integer 203050 can be stored as the sign data along with the exponents {000}.
98 = 90 + 9- 1- 213251 + 203250-203050= {121}{020}-{000}
In an implementation, the other rnodule(s) 122 may include an operations module
(not shown) to execute various arithmetic or other operations required for implementing the real-time applications. Once the MBNS representation of the input data is obtained from the memory 106, the operations module can execute the arithmetic operations, such as the ECC scalar

multiplication required for generating digital signatures. For generating a digital signature, typically a private key is multiplied with data such as identity information. When the MBNS representations for both the private key and the identity information are obtained, the operations module multiplies the private key and the identity information to obtain the digital signature in an efficient manner. Similarly, for the filter bank designs in mobile handsets and other tiny devices such as hearing aids, the operations module may be configured to perform various operations, such as transmit, receive, generate, and modulate discrete time signals based on the MBNS representations of data involved therein. In another example, for performing data compression, the operations module may perform encoding and decoding of the data based on the MBNS representations.
In one implementation, the operations module is implemented in the processor
102 and may include various components, such as adders and sign shifters, for executing the arithmetic operations. For instance, to compute multiplication of the private key 2a3b5c and the identity information 2d3e5f, the operations module 'a' with 'd', 'b! with V, and 'c' with 'f' to give the result of multiplication as 2a+d 3 b+e5c+f . Similarly, for dividing two multi-base numbers, the processors simply need to subtract exponents corresponding to the common base. Using the MBNS representations thus helps in reducing the complexity and time involved in executing the arithmetic operations as the processors now need to execute the arithmetic operations using less number of bits.
In one implementation, the input data is converted such that the MBNS
representation is in decreasing order of exponents without repetition of the n-integers, for example, integer 97 has a MBNS representation {121}{110}{000} in decreasing order of exponents without repetition of the n-integers.
Further, computational complexity for converting the input data, say a positive
integer 'n', to the MBNS representation using the system 100 is at most O (log n/log log n). Additionally, converting the input data in the MBNS representation also reduces the memory size and resources required to convert and store the number as compared to the memory and resources utilized by the other number systems, such as the traditional SBNS, as the input data is stored using only bits corresponding to the values of the exponents 'a', 'b', and V. Reducing the overall memory space, resources, in turn reduces power required by the system 100.

Fig. 2 illustrates a method 200 for processing data, in accordance with an
implementation of the present subject matter. In one implementation, the method 200 is a MBNS conversion method implemented for converting an input data from a-standard representation to a MBNS representation before being processed for real-time applications. The exemplary method 200 may be described in the general context of computer executable instructions. Generally, computer executable instructions can include routines, programs, objects, components, data structures, procedures, modules, functions, and the like that perform particular functions or implement particular abstract data types. The method may also be practiced in a distributed computing environment where functions are performed by remote processing devices that are linked through a communication network. In a distributed computing environment, computer executable instructions may be located in both local and remote computer storage media, including memory storage devices.
The order in which the method is described is not intended to be construed as a
limitation, and any number of the described method blocks can be combined in any order to implement the method, or an alternate method. Additionally, individual blocks may be deleted from the method without departing from the spirit and scope of the subject matter described herein. Furthermore, the method is not restricted to the present system 100 and can be implemented in any suitable hardware, software, firmware, or combination thereof.
At block 202, a first n-integer which is largest of n-integers less than or equal to
an input data is computed. In one implementation, the input data is received by a data processing system, such as the system 100. Further, the input data may be data required in various real-time applications, such as data security, digital signal processing (DSP), and data compression. For example, for ECC scalar multiplication, the input data may be a private key, a public key, or identity information represented in the form of numbers. Similarly, for applications in DSP, such as for the filter bank design in mobile handsets, the input data may be discrete time signals represented by a sequence of numbers or symbols. In one implementation, exponents of the first n-integer are stored in the memory 106, for example in the exponents data 136, for later retrieval. Consider an example where input data is say 97, then a first 3-integer which is largest of n-integers less than or equal to input data 97 will be 213251, i.e., 90. In this example, exponents {121} of the first n-integer 21 3251 are stored in the exponents data 136.

At block 204, a first difference between the input data and the first n-integer is
ascertained. In one implementation, the first n-integer is subtracted from the input data to ascertain the first difference, for example, 213251, i.e., 90 is subtracted from the input data 97 to ascertain the first difference equal to 7. In one implementation, the first difference module 114 ascertains the first difference between the input data and the first n-integer. In one implementation, the first difference module 114 subtracts the first n-integer from the input data in order to obtain the first difference.
At block 206, if the first difference is non-zero, then a maximum value for
exponent of each base of a next n-integer of the MBNS representation is determined. The maximum value is defined by a minimum of a stored exponent of corresponding base and one plus floor of log of the first difference in the corresponding base. In one implementation, the maximum value module 116 determines the maximum value. In one example, for input data equal to 97, the first 3-integer is say, 213251, i.e., 90 and thus the first difference is 97-90, i.e.. 7, Therefore, the maximum value for exponents of the next 3-integer is defined as:
Maximum value of a(n) = min {(a(n-l), 1 + Floor [Log2 (first difference)]}
Maximum value of b(n) = min {(b(n-l), 1 + Floor [Log3 (first difference)]}
Maximum value of c(n) = min {(c(n-l), 1 + Floor [Log5 (first difference)]}
Here, a(n), b (n), and c(n) are exponents of base 2, base 3, and base 5 respectively of the next 3-integer and are defined by the stored values {121} and the first difference 7 as indicated below:
Maximum value of a(n) = min (1,1 + Floor [Log2 7]} = min {I, 3} = 1
Maximum value of b(n) = min {2, 1 + Floor [Log37]} = min {2, 2} =2
Maximum value of c(n) = min {1,1+ Floor [Logs7)]} = min {1, 2} = I
At block 208, the next n-integer nearest to the first difference is computed with
exponents in a range of zero to the maximum value. In this way, the exponents of the next n-integer are computed in a predetermined range, and hence computation time is significantly reduced. In one implementation, the next n-integer module 118 computes, if the first difference is non-zero, the next n-integer nearest to the first difference with exponents in a range of zero to the maximum value of the corresponding base. In one example, for input data equal to 97, the first 3-integer is say, 213251, i.e., 90, the first difference is thus 97-90, i.e., 7, and thus exponents

are in range of {0 to 1,0 to 2, and 0 to 1}. In this example, the next 3-integer nearest to the first difference of 7 and based on predetermined range is 213150, i.e., 6. In addition, exponents of each base of the next n-integer are stored in the exponents data 136. In the above mentioned example, exponents {110} of the next 3-integer 213150 nearest to the first difference of 7 are stored in the exponents data 136. In one implementation, the next n-integer module 118 computes the next n-integer based on predefined computing rules, such as computing n-integers which are nonrepeating, i.e., a set of already stored exponents is not repeated in the MBNS representation of the input data. For example, if next 3-Integer nearest to 5 is 203051, i.e., 5 itself, but is already computed or stored, then preference may be given to say 2 3 5 +235, i.e., 4+1. In one implementation, the next n-integer nearest to the first difference can be greater that the first difference. In said implementation, a sign data may be used to keep track of sign of an n-integer (2a3b5c ...nx) of the MBNS representation. Consider an example: where input data is say 98; the
1 0 1 ■
first 3-integer is 2 3 5 , i.e., 90; and accordingly maximum allowed exponents for next 3-integer are {121}. In this example, the first difference of 8 can be represented as 9-1 and thus the next 3-integer is 2°325°, i.e., 9 which is greater than the first difference 8. In the end, input data 98 can be represented as 21325l + 203250-203°50, i.e., 90 + 9-1.
At block 210, a next difference between the first difference and the next n-integer
is ascertained. If the next difference is non-zero, then this next difference becomes the first difference and a loop is created that keeps on computing the next n-integer till the next difference becomes zero. In one example, for input data equal to 97, the first 3-integer is say, 21325l, i.e., 90, the first difference is thus 97-90, i.e., 7, range of next exponents is {0 - 1, 0 - 2, 0 - 1}, and the next 3-integer is 2l3 5° equal to 6. In said example, the next difference is 1 between the first difference 7 and the next n-integer 213150 equal to 6. In said example, the next difference of 1 becomes the first difference and the next 3-integer corresponding to 1 is computed which is 2 3 5 based on relevant maximum values. Like the previous exponents, exponents {000} are also stored in a memory. The MBNS representation of the input data can be obtained from the memory. In the above mentioned example, the MBNS representation for the input data 97 as obtained from the memory is {121}{310}{000}. As can be observed, the method 200 generates multi-base numbers with a decreasing order of exponents, which are useful in applications like ECC scalar multiplication, VLSI design, Inner-product computation unit, Mobile hardware platforms, etc.

Although implementations for the data processing system based on multi-base
numbers have been described in language specific to structural features and/or methods, it is to be understood that the invention is not necessarily limited to the specific features or methods described. Rather, the specific features and methods are disclosed as exemplary implementations for the data processing system based on multi-base numbers.

We Claim:
1. A computer implemented method for reducing memory usage comprising:
computing by a processor (102) a first n-integer, wherein the first n-integer is largest of n-integers less than or equal to an input data;
storing exponents corresponding to the first n-integer in a memory (106);
ascertaining a first difference between the input data and the first n-integer;
determining a maximum value for an exponent of each base of a next n-integer, wherein the maximum value is a minimum of the stored exponent of corresponding base and one plus floor of logarithm of the first difference in the corresponding base; and
computing by the processor (102) the next n-integer, wherein the next n-integer is nearest to the first difference, and wherein exponents corresponding to the next n-integer are in a range of zero to the maximum value of the corresponding base.
2. The method as claimed in claim 1 further comprising:
storing the exponents corresponding to the next n-integer in the memory (106);
ascertaining a next difference between the first difference and the next n-integer; and
assigning the next difference as the first difference when the next difference is nonzero.
3. The method as claimed in claim 1, wherein the next n-integer is greater than the first difference.
4. The method as claimed in claim 1. wherein the exponents corresponding to the next n-integer include values other than values of the stored exponents.
5. The method as claimed in claim 1 further comprising executing arithmetic operations based on the stored exponents,
6. The method as claimed in claim 1 further comprising extracting the stored exponents from the memory (106) to represent the input data in a Multi-Base Number System (MBNS) representation.
7. A system (100) comprising:
a processor (102); and
a memory (106) coupled to the processor (102). the memory (106) comprising:

a first n-integer module (112) configured to compute a first n-integer, wherein the first n-integer is largest of n-integers less than or equal to an input data, and store exponents corresponding to the first n-integer in the memory (106);
a first difference module (114) configured to ascertain a first difference between the input data and the first n-integer;
a maximum value module (116) configured to determine a maximum value for an exponent of each base of a next n-integer, wherein the maximum value a minimum of a stored exponent of corresponding base and one plus floor of logarithm of the first difference in the corresponding base;
a next n-integer module (118) configured to compute the next n-integer. wherein the next n-integer is nearest to the first difference, and wherein exponents corresponding to the next n-integer are in a range of zero to the maximum value of the corresponding base, and store the exponents corresponding to the next n-integer in the memory (106); and
a next difference module (120) configured to ascertain a next difference between the first difference and the next n-integer, and assign the next difference as the first difference when the next difference is non-zero.
8. The system (100) as claimed in claim 7, wherein the next n-integer module (118) is further configured to compute non repeating n-integers.
9. The system (100) as claimed in claim 7, wherein the next n-integer module (118) is further configured to compute the next n-integer greater than the first difference.
10. The system (100) as claimed in claim 9, wherein the memory (106) further comprises sign data to store a sign of the next difference.
11. The system (100) as claimed in claim 7, further comprising an operations module configured to execute arithmetic operations based on the stored exponents.
12. The system (100) as claimed in any one of the preceding claims, wherein the system (100) is implemented as at least one of a cryptography system, a data compression system, a mobile phone, a hearing aid, and an Elliptic Curve Cryptography (ECC) scalar multiplication system.
13. A computer-readable medium having embodied thereon a computer program for executing a method comprising:

computing by a processor (102) a first n-integer, wherein the first n-integer is largest of n-integers less than or equal to an input data;
storing exponents corresponding to the first n-integer in a memory (106);
ascertaining a first difference between the input data and the first n-integer;
determining a maximum value for an exponent of each base of a next n-integer, wherein the maximum value is a minimum of the stored exponent of corresponding base and one plus floor of logarithm of the first difference in the corresponding base;
computing by the processor (102) the next n-integer. wherein the next n-integer is nearest to the first difference, and wherein exponents corresponding to the next n-integer are in a range of zero to the maximum value of the corresponding base;
storing the exponents corresponding to the next n-integer in the memory (106);
ascertaining a next difference between the first difference and the next n-integer; and
assigning the next difference as the first difference when the next difference is nonzero.