स्क्वायर एंड मल्टीप्लाई एल्गोरिदम

Last updated on Aug 20, 2025

स्क्वायर एंड मल्टीप्लाई एल्गोरिथम $\mathcal{O}(\log n)$ (लॉगरिदमिक समय) में पूर्णांक घातांक (integer exponents) की गणना करता है। घातांक $x^n$ की गणना करने का सामान्य (naive) तरीका $x$ को स्वयं से $n$ बार गुणा करना है, जिसकी गणना में $\mathcal{O}(n)$ समय लगेगा।

मान लीजिए कि हम $x^{20}$ की गणना करना चाहते हैं। $x$ को स्वयं से 20 बार गुणा करने के बजाय, हम $x$ से शुरू करते हैं और इसे बार-बार स्क्वायर (वर्ग) करते हैं जब तक कि हम $x^{16}$ की गणना नहीं कर लेते:

\begin{align*} x^2&=x\cdot x\\ x^4&=x^2\cdot x^2\\ x^8&=x^4\cdot x^4\\ x^{16}&=x^8\cdot x^8 \end{align*}

ध्यान दें कि हम $x^{20}$ की गणना इस प्रकार कर सकते हैं:

x^{20}=x^4x^{16}

घातांक (exponents) के इस तरह से “जुड़ने” के तथ्य को बीजगणित (algebra) में प्रोडक्ट-ऑफ़-पावर्स रूल (product-of-powers rule) कहा जाता है।

यह लेख Uniswap V3 codebase पर एक श्रृंखला का हिस्सा है। Uniswap V3 एक tick index को square root price में बदलने के लिए स्क्वायर एंड मल्टीप्लाई एल्गोरिथम का उपयोग करता है। हालाँकि, यह लेख उन सभी के लिए भी है जो यह सीखना चाहते हैं कि स्क्वायर एंड मल्टीप्लाई एल्गोरिथम कैसे काम करता है।

स्क्वायर्ड एक्सपोनेंट्स सीक्वेंस

हम इस लेख में कई बार “स्क्वायर्ड-एक्सपोनेंट्स सीक्वेंस” (squared-exponents sequence) शब्द का उपयोग करेंगे, जो $x^1,x^2,x^4,x^8,\dots$ है। प्रत्येक पद पिछले पद का एक स्क्वायर (वर्ग) होता है। आधार (base) $x$ का कोई भी गैर-शून्य (non-zero) मान हो सकता है। उदाहरण के लिए, $0.7^1,0.7^2,0.7^4,...$ एक वैध स्क्वायर्ड-एक्सपोनेंट्स सीक्वेंस है। इसी तरह, $-1.56,-1.56^2,...,-1.56^{32},-1.56^{64}$ भी एक वैध स्क्वायर्ड-एक्सपोनेंट्स सीक्वेंस है।

फ्रैक्शनल बेस (fractional base) के साथ स्क्वायर और मल्टीप्लाई

यदि हमें पहले से पता है कि आधार (base) एक निश्चित मान (fixed value) होगा, और जिन घातांकों की हम संभवतः गणना कर सकते हैं उनकी एक ज्ञात ऊपरी-सीमा (upper-bound) है, तो हम पहले से स्क्वायर्ड-एक्सपोनेंट्स सीक्वेंस की गणना (precompute) कर सकते हैं और फिर गुणा करने के बजाय लुकअप (lookups) कर सकते हैं। उदाहरण के लिए, यदि हम $0.7^x$ की गणना करना चाहते हैं और हम पहले से जानते हैं कि $x$ , 63 से बड़ा नहीं होगा, तो हम निम्नलिखित मानों को प्रीकंप्यूट कर सकते हैं:

\begin{align*} &0.7\\ &0.7^2=0.49\\ &0.7^4=0.2401\\ &0.7^8=0.05764801\\ &0.7^{16}=0.00332329\\ &0.7^{32}=0.00001104 \end{align*}

फिर, उदाहरण के लिए, यदि हम $0.7^{44}$ की गणना करना चाहते हैं, तो हम स्क्वायर्ड एक्सपोनेंट सीक्वेंस से उपयुक्त प्रीकंप्यूटेड मानों को एक साथ इस प्रकार गुणा कर सकते हैं:

\begin{align*} 0.7^{44}&=0.7^{32}\times0.7^{8}\times0.7^{4}\\ 0.00000015&=0.00001104\times0.05764801\times0.2401 \end{align*}

पाठक को सलाह दी जाती है कि वे इसकी दोबारा जांच करने के लिए अपने कैलकुलेटर पर $0.7^{44}$ की गणना स्वयं करके देखें।

जब हम इस तरह से मानों को कैश (cache) करते हैं, तो हमें पहले से उस घातांक की ऊपरी सीमा (upper bound) पता होनी चाहिए जिसे हमारे एप्लिकेशन को संभालना है।

फ्रैक्शनल एक्सपोनेंट्स के साथ स्क्वायर एंड मल्टीप्लाई एल्गोरिथम

मान लीजिए कि $0.7^x$ की गणना करने के बजाय हम $\sqrt[3]{0.7^x}$ की गणना करना चाहते हैं? यह $0.7^{x/3}$ के बराबर है। हम अभी भी स्क्वायर-एंड-मल्टीप्लाई एल्गोरिथम का उपयोग कर सकते हैं क्योंकि घातांक एक स्थिर संख्या (constant number) से विभाजित होता है, इसलिए प्रोडक्ट-ऑफ़-पावर्स रूल अभी भी लागू होता है। दूसरे शब्दों में,

0.7^{44/3}=0.7^{32/3}\times0.7^{8/3}\times0.7^{4/3}

$0.7^{44/3}$ की गणना करने के लिए, हम $0.7$ की उन घातों (powers) को बदल देंगे जिन्हें हम निम्न प्रकार से प्रीकंप्यूट करते हैं:

\begin{align*} &0.7^{1/3}=0.8879040017426006\\ &0.7^{2/3}=0.7883735163105242\\ &0.7^{4/3}=0.6215328012198205\\ &0.7^{8/3}=0.38630302299215685\\ &0.7^{16/3}=0.14923002557287887\\ &0.7^{32/3}=0.02226960053248208 \end{align*}

फिर, $0.7^{44/3}$ की गणना करने के लिए हम प्रीकंप्यूटेड घातांकों को इस प्रकार गुणा करते हैं:

\begin{align*} 0.7^{44/3}&=0.7^{32/3}\times0.7^{8/3}\times0.7^{4/3}\\ 0.005346931087848946&=0.02226960053248208\times0.38630302299215685\times0.6215328012198205 \end{align*}

एक बार फिर, पाठक को सलाह दी जाती है कि वे इन गणनाओं को स्वयं करके देखें।

स्क्वायर्ड एक्सपोनेंट सीक्वेंस से तत्वों को चुनना

यदि हम $b^{44}$ की गणना करना चाहते हैं, तो हम यह कैसे पता लगाएंगे कि हमें अपने स्क्वायर्ड-एक्सपोनेंट्स सीक्वेंस से $b$ की किन घातों (powers) की आवश्यकता है? दूसरे शब्दों में, हम जल्दी से यह कैसे निर्धारित करें कि हमें $b^{32}, b^{8}, b^{4}$ की आवश्यकता है और $b^{32}, b^{4}, b^{1}$ की नहीं?

दिए गए लक्ष्य योग (target sum), जैसे कि 44, के लिए, हम जल्दी से यह कैसे निर्धारित करें कि 32, 8, और 4 योग हैं? वैकल्पिक रूप से, मान लीजिए कि हम $b^{37}$ की गणना करने का प्रयास कर रहे हैं। स्क्वायर्ड एक्सपोनेंट सीक्वेंस के जिन तत्वों की हमें आवश्यकता है वे $b^{32},b^{4},b^{1}$ हैं — हम जल्दी से यह कैसे निर्धारित करें कि हमें $b^{32},b^{4},b^{1}$ की आवश्यकता है और $b^{2},b^{8},b^{16}$ की नहीं?

एक सामान्य तरीका (naïve approach) यह होगा कि सबसे बड़े प्रीकंप्यूटेड एक्सपोनेंट से नीचे की ओर एक लीनियर सर्च (linear search) की जाए और उस सबसे बड़े एक्सपोनेंट को घटाया जाए जो लक्ष्य से अधिक (overshoot) न हो। उदाहरण के लिए, यदि हम $5^{44}$ की गणना कर रहे थे, तो इसका मतलब है कि हमने पहले ही 5 के स्क्वायर्ड एक्सपोनेंट सीक्वेंस की गणना कर ली है। हम नीचे की ओर स्कैन करते हैं और पाते हैं कि 32, 44 के सबसे करीब का मान है। फिर हम 16 को खोजने के लिए फिर से नीचे स्कैन करते हैं, लेकिन ध्यान दें कि 32+16 जोड़ने पर यह 44 से अधिक हो जाता है, इसलिए हम 16 को छोड़ देते हैं और 8 पर आगे बढ़ते हैं, और इसी तरह।

सम कंपोनेंट्स (sum components) को निकालने के लिए बाइनरी रिप्रेजेंटेशन का उपयोग करना

ऊपर बताए गए लीनियर सर्च का उपयोग करने के बजाय, हम यह देखकर अधिक कुशल (efficient) हो सकते हैं कि लक्ष्य घातांक (target exponent) का बाइनरी रिप्रेजेंटेशन हमें सटीक रूप से बताता है कि स्क्वायर्ड एक्सपोनेंट सीक्वेंस से किन तत्वों का उपयोग करना है।

इसे उदाहरणों द्वारा सबसे अच्छी तरह समझाया जा सकता है।

एक बाइनरी संख्या को डेसीमल (decimal) संख्या में बदलने के लिए, हम निम्नलिखित सूत्र का उपयोग करते हैं जहाँ $b_i$ बाइनरी संख्या में $i$ -th बिट है:

\text{decimal\_value}=2^{n-1}b_{n-1}\dots+8b_3+4b_2+2b_1+b_0=\sum_{i=0}^{n-1}2^ib_i

13 का बाइनरी मान 1101 है क्योंकि

\begin{align*} 44=8&\cdot1 \\ +4&\cdot1 \\ +2&\cdot0 \\ +1&\cdot1 \end{align*}

52 का बाइनरी मान 110100 है क्योंकि

\begin{align*} 52 = 32&\cdot1\\ +16&\cdot1\\ +8&\cdot0\\ +4&\cdot1\\ +2&\cdot0\\ +1&\cdot0 \end{align*}

इसलिए, यदि हम $b^{13}$ की गणना करना चाहते हैं, और हमारा स्क्वायर्ड एक्सपोनेंट सीक्वेंस $b^8,b^4,b^2,b^1$ है, तो हम 1011 के बाइनरी रिप्रेजेंटेशन को देख सकते हैं और यह निर्धारित कर सकते हैं कि हमें 8 एक्सपोनेंट, 4 एक्सपोनेंट, और 1 एक्सपोनेंट चुनना चाहिए, फिर गणना करें:

b^{13}=b^8\cdot b^4\cdot b^1

चूँकि

13=8+4+1

इस प्रकार, हम जल्दी से यह निर्धारित कर सकते हैं कि 13 को 8 + 4 + 1 के रूप में लिखा जा सकता है चूँकि 3rd बिट, 2nd बिट और 0th बिट 1 हैं।

यह पता लगाना कि कोई बिट सेट (set) है या नहीं

हम निम्नलिखित लॉजिक के साथ यह पता लगा सकते हैं कि किसी बाइनरी रिप्रेजेंटेशन में n-th बिट 1 है या नहीं:

function nthBitSet(uint256 x, uint8 n) public pure returns (bool isSet) {

	isSet = x & uint256(2)**n != 0;
}

2 की घातों (powers-of-two) के बाइनरी रिप्रेजेंटेशन पर विचार करें:

Power of two (2 की घात)	Decimal Value (डेसीमल मान)	Binary Representation (बाइनरी रिप्रेजेंटेशन)
2^0	1	00001
2^1	2	00010
2^2	4	00100
2^3	8	01000
2^4	16	10000

uint256(2)**n एक ऐसी संख्या बनाता है जिसमें केवल nth बिट 1 पर सेट होती है। उदाहरण के लिए, यदि n = 3 है, तो यह बाइनरी मान 1000 उत्पन्न करेगा। $2^3=8$ है और 1000, 8 का बाइनरी रिप्रेजेंटेशन है, जैसा कि ऊपर दी गई तालिका में दिखाया गया है। यदि x और 2^n का बिटवाइज़ AND (bitwise AND) शून्य नहीं है, तो isSet, true होता है।

बिटवाइज़ AND (Bitwise AND) कैसे काम करता है

बिटवाइज़ AND केवल तभी 1 लौटाता है जब दोनों संबंधित (corresponding) बिट्स 1 हों; अन्यथा, यह 0 लौटाता है। उदाहरण के लिए, 8 & 13 = 8 क्योंकि 8 का बाइनरी रिप्रेजेंटेशन 1000 है और 13 का बाइनरी रिप्रेजेंटेशन है:

\begin{aligned}13 &= 1 \cdot 2^3 \\ &+ 1 \cdot 2^2 \\ &+ 0 \cdot 2^1 \\ &+ 1 \cdot 2^0\end{aligned}

या 1101। जब हम 1000 को 1101 के साथ बिटवाइज़ AND करते हैं तो हमें 1000 मिलता है क्योंकि 8 और 13 दोनों में 3rd स्थान पर एक समान 1-बिट (common 1-bit) होता है।

इसे नीचे दर्शाया गया है:

Suppose x = 13 (binary: 1101) and n = 3:

x           = 1101 (decimal 13)
2**n        = 1000 (decimal 8)
------------------------------
bitwise AND = 1000 (decimal 8) != 0, thus true.

Thus, nthBitSet(13, 3) returns true.

चूँकि अंतिम परिणाम 1000 शून्य के बराबर नहीं है, इसलिए हम जानते हैं कि x और 2^n के बीच 1 बिट्स की ओवरलैपिंग (overlapping) अवश्य हुई होगी — यह इंगित करता है कि वह बिट एक के बराबर होनी चाहिए।

उदाहरण 2: क्या 13 में 1st बिट सेट है? हम नीचे दिखाए अनुसार पहली बिट के लिए 2**1 के रूप में एक “मास्क” (mask) बना सकते हैं:

Suppose x = 13 (binary: 1101) and n = 1:

x           = 1101 (decimal 13)
2**n        = 0010 (decimal 2)
------------------------------
bitwise AND = 0000 (decimal 0) == 0, thus false.

Thus, nthBitSet(13, 1) returns false.

चूँकि अंतिम परिणाम 0000 है, हम जानते हैं कि 1st बिट सेट नहीं है।

उदाहरण 3: क्या 13 में 0th बिट सेट है?

Suppose x = 13 (binary: 1101) and n = 0:

x           = 1101 (decimal 13)
2**n        = 0001 (decimal 1)
------------------------------
bitwise AND = 0001 (decimal 1) == 1, thus true.

Thus, nthBitSet(13, 0) returns true.

$0.7^x$ का Python उदाहरण

अब हम 0.7 की घात को 32 तक बढ़ाने वाले निम्नलिखित फ़ंक्शन को बनाने के लिए अपने द्वारा सीखी गई हर चीज़ को मिलाते हैं:

pow1 = 0.7
pow2 = 0.48999999999999994 # 0.7^2
pow4 = 0.24009999999999995 # 0.7^4
pow8 = 0.05764800999999997 # 0.7^8
pow16 = 0.0033232930569600965 # 0.7^16

def raise_07_to_p(p):
	# computes 0.7^p
	assert p < 32
	
	# if p = 0, we return 1, which is correct
	# since 0.7^0 = 1
	accumulator = 1
	
	if p & 1 != 0:
		accumulator = accumulator * pow1
	if p & 2 != 0:
		accumulator = accumulator * pow2
	if p & 4 != 0:
		accumulator = accumulator * pow4
	if p & 8 != 0:
		accumulator = accumulator * pow8
	if p & 16 != 0:
		accumulator = accumulator * pow16

	return accumulator

# check correctness
print(0.7**14, raise_07_to_p(14))
print(0.7**18, raise_07_to_p(18))
print(0.7**30, raise_07_to_p(30))

उपरोक्त कोड केवल 0.7 की उन घातों (powers) का उपयोग करके बार-बार गुणा करने से बचाता है जो घातांक (exponent) के बाइनरी रिप्रेजेंटेशन में 1s से मेल खाती हैं।

अब तक, हमने सामान्य/फ्लोटिंग-पॉइंट नंबरों (floating-point numbers) का उपयोग किया है। हालाँकि, स्मार्ट कॉन्ट्रैक्ट्स (smart contracts) जैसे वास्तविक दुनिया के सिस्टम में, हम अक्सर फिक्स्ड-पॉइंट नंबरों (fixed-point numbers) (या Q-numbers) का उपयोग करते हैं।

फिक्स्ड-पॉइंट नंबरों के साथ स्क्वायर एंड मल्टीप्लाई एल्गोरिथम का उपयोग करना

फिक्स्ड-पॉइंट नंबरों (या Q-numbers) को एक साथ गुणा करने के बाद, परिणाम को “नॉर्मलाइज़” (normalized) किया जाना चाहिए, अर्थात, परिणाम को स्केलिंग फैक्टर (scaling factor) से विभाजित करने की आवश्यकता होती है। उदाहरण के लिए, जब हम दो 18-डेसीमल फिक्स्ड-पॉइंट नंबरों को एक साथ गुणा करते हैं, तो हमें परिणाम को $10^{18}$ से विभाजित करना होता है, अन्यथा अंतिम परिणाम 36 डेसीमल के साथ लिखा जाएगा।

प्रीकंप्यूटेड स्क्वायर और मल्टीप्लाई का Python और Solidity इम्प्लीमेंटेशन — फिक्स्ड-पॉइंट नंबरों के साथ

हम पहले Python में स्क्वायर एंड मल्टीप्लाई एल्गोरिथम को लागू (implement) करेंगे, फिर उस कोड को Solidity में अनुवाद करेंगे। Solidity संस्करण फिक्स्ड-पॉइंट नंबरों का उपयोग करेगा क्योंकि Solidity में फ्लोटिंग पॉइंट नहीं होते हैं। नीचे, हम संदर्भ कार्यान्वयन (reference implementation) के रूप में 128-बिट फिक्स्ड पॉइंट Q नंबर्स के रूप में 0.7 की घातों की गणना करने के लिए Python का उपयोग करते हैं:

from decimal import *
import math
getcontext().prec = 100

for i in [1,2,4,8,16,32]:
    print(f"0.7^{i} * 2**128 =", math.floor(Decimal(0.7) ** Decimal(i) * Decimal(2**128)))

जब हम ऊपर दिए गए कोड को रन करते हैं, तो हमें निम्नलिखित स्थिरांक (constants) मिलते हैं:

(base) ➜ python sqmul.py
0.7^1 * 2**128 = 238197656844656909312789480019373064192
0.7^2 * 2**128 = 166738359791259825940851714385556537344
0.7^4 * 2**128 = 81701796297717304344478436853479174360
0.7^8 * 2**128 = 19616601291081919795097291374069314602
0.7^16 * 2**128 = 1130858027394302849221997646234907220
0.7^32 * 2**128 = 3758172630847077410107089115980415

स्क्वायर और मल्टीप्लाई का Solidity इम्प्लीमेंटेशन

नीचे दिया गया Solidity इम्प्लीमेंटेशन 128-बिट फिक्स्ड-पॉइंट नंबरों का उपयोग करता है, जिसका अर्थ है कि संख्या के बाद 128 बिट्स हैं, या समान रूप से, फ्रैक्शनल नंबर (fractional number) को $2^{128}$ से गुणा करके स्केल अप (scaled up) किया गया है। >> 128 ऑपरेशन $2^{128}$ से भाग देने के बराबर है।

contract SquareAndMultiply {

    // z7_x means 0.7^x
    uint256 constant z7_1 = 238197656844656909312789480019373064192;
    uint256 constant z7_2 = 166738359791259825940851714385556537344;
    uint256 constant z7_4 = 81701796297717304344478436853479174360;
    uint256 constant z7_8 = 19616601291081919795097291374069314602;
    uint256 constant z7_16 = 1130858027394302849221997646234907220;
    uint256 constant z7_32 = 3758172630847077410107089115980415;

    function powZ7(uint256 e) public pure returns (uint256) {
        require(e < 64, "e too large");

        // if e is zero, return 1 as a 128-bit fixed point number
        uint256 acc = 1 << 128;

				// powers of 2 are written in hex, 0x10 = 16 and 0x20 = 32
        if (e & 0x1 != 0) acc = (acc * z7_1) >> 128;
        if (e & 0x2 != 0) acc = (acc * z7_2) >> 128;
        if (e & 0x4 != 0) acc = (acc * z7_4) >> 128;
        if (e & 0x8 != 0) acc = (acc * z7_8) >> 128;
        if (e & 0x10 != 0) acc = (acc * z7_16) >> 128;
        if (e & 0x20 != 0) acc = (acc * z7_32) >> 128;

        // check the answer by doing acc / 2**128
        // in a language that has floating points
        // then check that equals 0.7^e
        return acc;
    }
}

केवल एक एक्सपोनेंट ऑपकोड (exponent opcode) का उपयोग क्यों नहीं करते?

जब किसी पूर्णांक (integer) को पूर्णांक घात (integer power) तक बढ़ाया जाता है, तो वर्चुअल मशीन के इन-बिल्ट ऑपकोड (built-in opcode) का उपयोग करना आमतौर पर अधिक कुशल होता है।

हालाँकि, इस ऑपकोड में ऊपर वर्णित नॉर्मलाइज़ेशन (normalization) चरण शामिल नहीं है। इसलिए, यदि $b^x$ में $b$ या $x$ में से कम से कम एक फिक्स्ड-पॉइंट नंबर है, तो हम वर्चुअल मशीन के exp ऑपकोड का उपयोग नहीं कर सकते।

Uniswap V3 में स्क्वायर एंड मल्टीप्लाई

एक tick को square root price में बदलने के लिए, Uniswap V3 को गणना करनी चाहिए:

\texttt{sqrtPrice}=\sqrt{1.0001^\text{i}}

(sqrtPrice के एक Q64.96 नंबर होने के कारण कुछ सुधारों के साथ)। चूँकि

आधार (base) स्थिर है और एकमात्र चर (variable) घातांक है और
ticks की रेंज पहले से ज्ञात है। Uniswap V3 स्क्वायर एंड मल्टीप्लाई एल्गोरिथम का उपयोग कर सकता है (और करता है)। इसे अगले अध्याय में समझाया गया है।

एक टीज़र के रूप में, यहाँ Uniswap V3 Tickmath Library से getSqrtRatioAtTick() का एक स्क्रीनशॉट दिया गया है। यह हमारे द्वारा ऊपर लिखे गए Solidity कोड के काफी समान दिखना चाहिए। उच्च स्तर पर, यह फ़ंक्शन जाँचता है कि क्या absTick में कोई बिट सेट है, और यदि है, तो यह ratio को 1.0001 की एक प्रीकंप्यूटेड घात से गुणा करता है।