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 DOUBLE-BASE NUMBERS
2. Applicants)
NAME NATIONALITY ADDRESS
TATA CONSULTANCY Indian Nirmal Building, 9th Floor, Nariman Point,
SERVICES LIMITED 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 double-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) has been introduced for
various applications which generally involve large numbers and complex calculations. The DBNS utilizes two bases to represent a number. Generally, first two prime numbers, i.e., 2 and 3 can be chosen as the bases for the DBNS. A typical DBNS representation for integer 127 can be
2233 + 2132 + 2030 or 2233 + 2430 + 2031 or 2531 + 2033 + 2230. Clearly , these represntations are
highly redundant as one integer can have multiple DBNS representations. The DBNS representations with the minimum number of sets of 2-integers (2a3b) are called optimum DBNS representations' as they consume fewer bits. Finding the optimum DBNS representation from various possible DBNS representations may be a time and resource consuming process, for example, integer 127 can have 783 DBNS representations, among which only three are optimum representations having only three 2-integers. As the numbers grow, finding the optimum DBNS representations from various possible representations becomes more difficult, for example, the integer 1000 can have 1295579 DBNS representations.
Many theoretical approaches have been proposed for representing a number into
the DBNS representation. 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 double-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 2-integer which is largest of 2-integers less
than or equal to an input data. The first 2-integer is computed based on a number of bits required to represent the input data. Further, exponents corresponding to first 2-integer are stored in a memory. Further, a maximum value for an exponent of each base of a next 2-integer is determined as a minimum of a stored exponent of corresponding base and one plus floor of logarithm of a first difference, between the input data and the first 2-integer, in the corresponding base. The method further includes computing the next 2-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 double-base numbers.
In recent years, the Double-Base Number System (DBNS) 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 DBNS is due to the fact that a DBNS representation generally utilizes fewer bits as compared to a traditional Single-Base Number System (SBNS) representation of a number. Thus, processing systems which are based on the DBNS could be preferred for certain complex operations.
In addition, the DBNS has proved to be efficient in executing arithmetic
operations, such as addition, subtraction, and multiplication. Efficiency in executing the arithmetic operations allows the DBNS 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 DBNS 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 DBNS 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 double-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, 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 DBNS representation in the form Σ2a3b, i.e., as a sum of one or more 2-integers of the form 2a3b.
In an implementation, a first 2-integer which is largest of 2-integers less than or
equal to the input data is computed with exponents in a range based on a number of bits required to represent the input data. The exponents corresponding to the first 2-integer are stored in a memory, such as a stack memory. For example, a first 2-integer which is largest of 2-integers less than or equal to less than or equal to the input data say 23, is say 2'32, i.e., 18, and exponents {12} corresponding to the 2-integer 2132 are stored in the memory. In this example, the exponents {12} are within a range based on a number of bits required to represent the input data 23. The number of bits required to represent the input data 23 are 5 as 23 equals to (10111)2. In one implementation, the range is from zero to floor of the number of bits divide by two. Thus, the range is zero to floor of 5/2, i.e., zero to 2 in the above mentioned example.
In said implementation, a first difference between the input data and the firsl 2-
integer is ascertained. In the above mentioned example, the first difference between the input data 23 and the first 2-integer 2132, i.e., 38 is 5. Further, if the first difference is non-zero, then a maximum value for an exponent of each base of a next 2-integer of the DBNS 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 5 and thus non-zero. Accordingly, the maximum value for exponents of next 2-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)]}
Here, a(n) and b (n) are exponents of base 2 and base 3 respectively of the next 2-integer and are defined by the stored values {12} and the first difference 5 as indicated below:

Maximum value of a(n) = min {1,1+ Floor [Log2 5]} = min {1, 3} = 1
Maximum value of b(n) = min {2, 1 + Floor [Log3 5]} = min {2, 2} = 2
In said implementation, if the first difference is non-zero, then the next 2-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 2-integer nearest to the first difference of 5 is 2031, i.e., 3 with exponents in range of 0 to 1 and 0 to 2, The exponents of the next 2-integer are stored in the memory, such as the previously discussed stack memory. In the above mentioned example, exponents {01} of the next 2-integer 2031 nearest to the difference of 5 are stored in the memory.
Further, a next difference between the first difference and the next 2-integer is
ascertained. In the above mentioned example, the next difference between the first difference 5 and the next 2-integer 2°31, i.e., 3 is 2. 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 2-integers till the next difference becomes zero. In the above mentioned example, the next difference of 2 becomes the first difference and the next 2-integer corresponding to 2 is computed based on determined maximum values. The maximum values will be based on stored values {01} and the first difference which is 2 now, As per the equation discussed above, the maximum values will be {01}. Hence, the next 2-Integer nearest to 2 is 2°3°, i.e., 1 based on the maximum values. Like the previous exponents, exponents {00} are also stored in the stack memory. In the end, the DBNS representation of the input data can be obtained from the stack memory. In the above mentioned example, the DBNS representation for the input data 23 as obtained from the stack memory is {12}{01}{00}{00}, i.e., 18+3+1 + 1. As can be observed, in the above mentioned example, the systems and methods, according to the present subject matter, generate double-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.
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 DBNS 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 similar tiny devices where chip area is 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 DBNS, say 2a3 and 2c3d, the processors simply need to add exponents corresponding to a common base, In the above example, the processor needs to add 'a' with 'c' and 'b' with 'd' to compute the multiplication as 2a+c3b+d. Similarly, for dividing two numbers represented in the form of the DBNS, the processors simply need to subtract exponents corresponding to the common base.
While aspects of systems and methods for data processing based on double-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 a 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 a 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 gignal 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 2-integer module 112, a first difference module 114, a

maximum value module 116, a next 2-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 2-integer data 126, first difference data 128, maximum value data 130, next 2-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 DBNS 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 DBNS representation. Using the DBNS representation, in the cryptography system, reduces computational time and resources as the DBNS 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 DBNS representation. Using the DBNS representation, in the mobile phones improves its efficiency and response time as the DBNS 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 DBNS representation for ECC scalar multiplication reduces computational complexity involved therein.

In one example, an integer is a 2-integer if its prime divisors are the first two
prime numbers, i.e., 2 and 3. The 2-integer is represented as 2a3b and is a single summand of a typical DBNS representation given below:

The system 100 processes the input data to provide the DBNS representation in
the form Σ2a3b, i.e., as a sum of one or more 2-integers of the form 2a3b.
The first 2-integer module 112 receives the input data to compute the first 2-
integer which is largest of 2-integers less than or equal to the input data. For example, if integer 77 is received as the input data, then the first 2-integer can be 2 3 , i.e., 72.
Since the first 2-integer serves as a largest 2-integer of the DBNS representation,
therefore, keeping the first 2-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 22-integer less than the input data will consume less memory as compared to memory consumed by the first 2-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 2-integer is always computed as a largest 2-integer less than or equal to the input data.
In addition, the first 2-integer module 112 is configured to compute the first 2-
Integer with exponents in a range based on number bits required to represent the input data. In one implementation, the range is from zero to floor of the number of bits divide by two. For instance in the above mentioned example, the input data is 77 which can be represented using 7 bits as (1001101)2, therefore, the range is from zero to floor of 7/2, i.e., zero to 3, i.e., the first 2-integer can have exponents in the range {0-3, 0-3} and thus 2332, i.e., 72 as the first 2-integer is valid. In one implementation, the first 2-integer module 112 stores the first 2-integer in the first 2-integer data 126.

Further, the first 2-integer module 112 is configured to store values of exponents
{al, bl} corresponding to the first 2-integer in the exponents data 136. In one implementation, the exponents corresponding to the first 2-integer are stored in a stack type of memory. For instance in the above mentioned example, the first 2-integer module 112 computes the first 2-integer as 2332, i.e., 72, then the exponents {32} are stored in the memory, for example, in the exponents data 136.
Upon computation of the first 2-integer, the first difference module 114 ascertains
the first difference between the input data and the first 2-integer. In one implementation, the first difference module 114 subtracts the first 2-integer from the input data in order to obtain the first difference. In above mentioned example, the first difference module 114 ascertains a first difference of 5 between the input data, 77, and the first 2-integer 2 3 , i.e., 72. In one implementation, the first difference module 114 stores the first difference in the first difference |jata 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 2-integer of the DBNS representation. In one implementation, the maximum value module 116 stores the maximum value in the maximum value data 130. In one implementation, 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. For example, the maximum values for exponents of the next 2-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)]}
Here, a(n) and b (n) are exponents of base 2 and base 3 respectively of the next 2-integer. In the above mentioned example, the maximum values of exponents corresponding to the next 2-integer are defined by the stored values {32} and the first difference of 13 as indicated below:
Maximum value of a(n) = min {3, 1 + Floor [Log2 5]} = min {3, 3} = 3
Maximum value of b(n) = min {2, 1 + Floor [Log3 5]} = min {2, 2} = 2
When the first difference is non-zero, then the next 2-integer module 118
computes the next 2-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. In the above mentioned example, the next 2-integer nearest to the first difference of 5 is 2 3 , i.e., 3 with exponents in range of 0 to 3 and 0 to 2. In one implementation, the next 2-integer module 118 stores the next 2-integer in the next 2-integer data 132. In one implementation, the next 2-integer module 118 stores an exponent of each base of the next 2-integer in the exponents data 136. In the above mentioned example, exponents {01} of the next 2-integer 2°31, i.e., 3 nearest to the difference of 5 are stored in a memory, such as previously discussed the stack memory where exponents of the first 2-integer are also stored. In one implementation, the next 2-integer module 118 computes the next 2-integer. In one implementation, the next 2-integer module 118 may also include predefined computation rules, such as computing 2-integers which are non-repeating, i.e., a set of already stored exponents is not repeated in the DBNS representation of the input data.
Further, the next difference module 120 ascertains the next difference between the
first difference and the next 2-integer. In one implementation, the next difference module 120 stores the next difference in the next difference data 134. In the above mentioned example, the next difference between the first difference 5 and the next 2-integer 2 31, i.e., 3 is 2. The exponents {01} are stored in the exponents data 136. When the next difference is non-zero, the next difference can be taken as the first difference for computing the next 2-integer. The cycle is repeated again with the next difference take as the first difference. In the above mentioned example, the next difference of 2 would be taken as the first difference. In such a case, the maximum value module 116 determines, based on first difference 2 and stored exponents {01}, maximum values for representation of 2 as {01}, Based on the maximum value, the next 2-integer module 118 computes the next 2-integer nearest to 2 as 2°3 . Like the previous xponents, exponents {00} are also stored in the exponents data 136. Again, the next difference of 1 becomes the first difference. Finally, the DBNS representation of the input data is obtained from the memory. In the above mentioned example, the DBNS representation of 77 obtained from the exponents data 136 is {32}{01}{00}{00}, i.e., 72+3+1+1. As can be observed, in the above mentioned example, the systems and methods, according to the present subject matter, generate double-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.

In an implementation, the DBNS representation can be in the form (2al3b) +
(2a23b2) ± ...(2an3bn). In such a case, sign data (not shown) may be used to keep track of the sign of an 2-integer (2a3b) of the DBNS 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 2-integer can be greater than the first difference.
Consider an example: where input data is say 77; the first 2-integer is 2 3 , i.e., 72; and accordingly maximum allowed exponents for next 2-integer are {32}. In this example, the first difference of 5 can be represented as 6-1 and thus the next 2-integer is 213l, i.e., 6 which is greater than the first difference 5. In the end, input data 77 can be represented as 2 3 +23 -2030,i.e., 72 + 6-1.
In one implementation, the sign data may be stored along with the exponents. For
Instance in the example given below, negative sign of the 2-integer 2 3 can be stored as the sign data along with the exponents {00}.
77 = 72 + 6-l=2332 + 2t31-2°3°={32}{ll}-{00}
In an implementation, the others module(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 DBNS 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 DBNS representations for both the private key and the identity information are obtained, the operations inodule '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 DBNS 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 DBNS 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 2a3b and the identity information 2c3d, the operations module 'a' with 'c' and 'b' with 'd' to give the result of multiplication as 2a+c3b+d. Similarly, for dividing two multi-base numbers, the processors simply need to subtract exponents corresponding to the common base. Using the DBNS 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 Jess number of bits.
In one implementation, the input data is converted such that the DBNS
representation is in decreasing order of exponents without repetition of the 2-integers, for example, integer 77 has a DBNS representation 2332 + 2*3' - 2°3° or {32}{11}-{00} in decreasing order of exponents without repetition of the 2-integers.
Further, computational complexity for converting the input data, say a positive
integer 'n' to the DBNS representation using the system 100 is at most O (log n/log log n). Additionally, converting the input data in the DBNS 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' and 'b', Reducing the overall memory space, resources, in turn reduces power required by the system 100.
Fig. 2 illustrates an exemplary method 200 for processing data, in accordance
with an implementation of the present subject matter. In one implementation, the method 200 is a DBNS conversion method implemented for converting an input data from a standard representation to a DBNS 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 2-integer which is largest of 2-integers less than or equal to
input data is computed with exponents in range based on number of bits required to represent the input data. 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, luch 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. Further, the first 2-integer which is largest of 2-integers less than or equal to the input data is computed based on the number of bits required to represent the input data. The number of bits is utilized in determining maximum possible values of exponents of the first 2-integer and thus in reducing time involved in computing the first 2-integer. In one implementation, exponents of the first 2-integer fall within a range from zero to floor of the number of bits divide by 2. For example, input data 86 can be represented in 7 bits as (1010110)2; accordingly, the exponents of the first 2-integer less than or equal to the input data 86 fall within a range from zero to floor of 7/2, i.e., zero to 3; and therefore, 2332, i.e., 72 becomes first 2-integer for the input data 86. In one implementation, the exponents corresponding to the first 2-integer are stored in memory, more particularly in the exponents data 136, for later retrieval. For example, exponents {32} of the first 2-integer 2332 are stored in the exponents data 136. In one implementation, the first 2-integer module 112 computes the first 2-integer based on the number of bits.

At block 204, a first difference between the input data and the first 2-integer is
ascertained. In one implementation, the first 2-integer is subtracted from the input data to ascertain the first difference, for example, 2332, i.e., 72 is subtracted from the input data say 86 to ascertain the first difference equal to 14. In one implementation, the first difference module 114 ascertains the first difference between the input data and the first 2-integer. In one implementation, the first difference module 114 subtracts the first 2-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 2-integer of the DBNS 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 the above mentioned example, for input data equal to $6, the first 2-integer is 2332, i.e., 72 and thus the first difference is 86-72, i.e., 14, Therefore, the maximum value for exponents of the next 2-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)]}
Here, a(n) and b (n) are exponents of base 2 and base 3 respectively of the next 2-integer and are defined by the stored values {32} and the first difference 14 as indicated below:
Maximum value of a(n) = min {3, 1 + Floor [Log2 14]} = min {3, 4} = 3
Maximum value of b(n) = min {2, I + Floor [Log314]} =min {2, 3} = 2
At block 208, the next 2-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 2-integer are computed in a predetermined range, and hence computation time is significantly reduced. In one implementation, the next 2-integer module 118 computes, if the first difference is non-zero, the next 2-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 86, the first 2-integer is say, 2332, i.e., 72, the first difference is thus 86-72, i.e., 14, and exponents of the next-2integer are in predetermined range of {0 to 3, 0 to 2}. In this example, the next 2-integer nearest to the first difference of 14 and based on the predetermined range is 223! i.e., 12. In

addition, exponents of each base of the next 2-integer are stored in the exponents data 136. In the above mentioned example, exponents {21} of the next 2-integer 22 31 . i.e., 12 nearest to the difference of 14 are stored in the exponents data 136. In one implementation, the next 2-integer module 118 computes the next 2-integer based on predefined computing rules, such as computing 2-integers which are non-repeating, i.e., a set of already stored exponents is not repeated in the DBNS representation of the input data. For example, if next 2-integer nearest to 6 is 2131, i.e., 6 itself, but is already computed or stored, then preference may be given to say 2031, i.e., 3. In one implementation, the next 2-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 2-integer (2a3b) of the DBNS representation. Consider an example: where input data is say 77; the first 2-integer is 2332 , i.e., 72; and accordingly maximum allowed exponents for next 2-integer are {32}. In this example, the first difference of 5 can be represented as 6-1 and thus the next 2-integer is 2131, i.e., 6 which is greater than the first difference 5. In the end, input data 77 can be represented as 2 3 + 213l -2030, i.e., 72 + 6 - 1. In one implementation, the sign data may be stored along with the exponents. For instance in the example given below, negative sign of the 2-integer 2°3 can be stored as the sign data along with the exponents {00}.
77 = 72 + 6-l=2332+2131-2°3°={32}{ll}-{00}
At block 210, a next difference between the first difference and the next 2-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 2-integer when the next difference becomes zero. In one example, for input data equal to 86, the first 2-integer is say, 2 3 , i.e., 72, the first difference is thus 86-72, i.e., 14, range of exponents of the next 2-integer is {0 - 3, 0 - 2} and the next 2-integer is 2 3 , i.e., 12. In said example, the next difference is 2 between the first difference 14 and the next 2-integer 2231, i.e., 12. In said example, the next difference of 2 becomes the first difference and the next 2-integer corresponding to 2 is computed which is 2 3 based on determined maximum values. Like the previous exponents, exponents {10} are also stored in the exponents data 136. The DBNS representation of the input data can be obtained from the exponents data 136. In the above mentioned example, the DBNS representation for the input data 86 as obtained from the memory is {32}{21}{10}. As can be observed, the method 200 generates double-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 data processing based on double-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 based on double-base numbers.

We claim:
1. A computer implemented method for reducing memory usage comprising:
computing by a processor (102) a first 2-integer, wherein the first 2-integer is largest of 2-integers less than or equal to an input data, and wherein the first 2-integer is computed based on a number of bits required to represent the input data;
storing exponents corresponding to the first 2-integer in a memory (106);
ascertaining a first difference between the input data and the first 2-integer;
determining a maximum value for an exponent of each base of a next 2-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 2-integer nearest to the first difference, wherein exponents corresponding to the next 2-integer are in a range of zero to the maximum value of the corresponding base. The method as claimed in claim 1 further comprising:
storing the exponents corresponding to the next 2-integer in the memory (106);
ascertaining a next difference between the first difference and the next 2-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 exponents corresponding to the first 2-integer are in a predetermined range from zero to floor of the number of bits divide by 2.
4. The method as claimed in claim 1, wherein the exponents corresponding to the next 2-integer include values other than values of the stored exponents.
£. 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 comprises extracting stored exponents from the memory (106) to represent the input data in a Double-Base Number System (DBNS) representation.
7. The method as claimed in claim 1, wherein the next 2-integer is greater than the first difference.
8. A system (100) comprising:

a processor (102); and
a memory (106) coupled to the processor (102), the memory (106) comprising:
a first 2-integer module (112) configured to compute a first 2-integer, wherein the first 2-integer is largest of 2-integers less than or equal to an input data, and store exponents corresponding to the first 2-integer in the memory (106);
a first difference module (114) configured to ascertain a first difference between the input data and the first 2-integer;
a maximum value module (116) configured to determine a maximum value for an exponent of each base of a next 2-integer, wherein the maximum value is 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 2-integer module (118) configured to compute the next 2-integer nearest to the first difference, wherein exponents corresponding to the next 2-integer are in a range of zero to the maximum value of the corresponding base, and store the exponents corresponding to the next 2-integer in the memory (106); and
a next difference module (120) configured to ascertain a next difference between the first difference and the next 2-integer, and assign the next difference as the first difference when the next difference is non-zero.
9. The system (100) as claimed in claim 8, wherein the exponents corresponding to the first 2-integer are in a predetermined range from zero to floor of the number of bits divide by 2,
10. The system (100) as claimed in claim 8 further comprising an operations module configured to execute arithmetic operations based on the stored exponents.
11. The system (100) as claimed in claim 8, wherein the next 2-integer module (118) is further configured to compute non-repeating 2-integers.
12. The system (100) as claimed in claim 8, wherein the next 2-integer module (118) is further configured to compute the next 2-integer, and wherein the next 2-integer is greater than the first difference.
13. The system (100) as claimed in claim 12, wherein the memory (106) further comprises sign data for to store a sign of the next difference.

14. 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.
15. A computer-readable medium having embodied thereon a computer program for executing a method comprising:
computing by a processor (102) a first 2-integer, wherein the first 2-integer is largest of 2-integers less than or equal to an input data, and wherein the first 2-integer is computed based on a number of bits required to represent the input data;
storing exponents corresponding to the first 2-integer in a memory (106);
ascertaining a first difference between the input data and the first 2-integer;
determining a maximum value for an exponent of each base of a next 2-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 2-integer nearest to the first difference, wherein exponents corresponding to the next 2-integer are in a range of zero to the maximum value of the corresponding base;
storing the exponents corresponding to the next 2-integer in the memory (106);
ascertaining a next difference between the first difference and the next 2-integer; and
receiving the next difference as the first difference when the next difference is nonzero.