6 रजिस्टरों के साथ अहस्ताक्षरित पूर्णांकों पर डिवीजन और मोडुलो

Dec 02 2020

मुझे अधिकतम 6 रजिस्टरों (a, b, c, d, e, f) का उपयोग करते हुए दो अहस्ताक्षरित पूर्णांक N1 और N2 ([दोनों हैं> = 0) सकारात्मक या 0 को विभाजित करने के लिए लॉग टाइम एल्गोरिथ्म (एक वर्चुअल मशीन के लिए) खोजना होगा। जहां यदि विभक्त 0 है तो परिणाम 0 और मॉडुलो ऑपरेशन है।

div -> N1 / N2
mod -> N1% N2

जैसी आज्ञाओं के साथ

RESET a -> a = 0
ADD ab -> a = a + b
SUB ab -> a = अधिकतम (0, ab)
SHR a -> a = फ्लोर (a / 2)
SHL a -> a = फ्लोर (एक * 2)
INC a -> a + = 1 है
DEC a -> a = मैक्स (0, ए -1)
JUMP j -> j-th लाइन पर जाएं
JZERO xj -> यदि x 0 से कूदने के लिए k + j है
JODD xj -> यदि x k + j से कूदने की तुलना में विषम है

क्या कोई एल्गोरिदम है जो मेरी मदद कर सकता है?

मैं केवल तभी जांच सकता हूं कि क्या reg में मान ODD या ZERO है।

मदद के लिए शुक्रिया।

जवाब

1 PeterCordes Dec 02 2020 at 18:34

संतृप्त-घटाना और jzeroकम-से-या-बराबर (या अधिक-से-अधिक) के लिए तुलना करने की अनुमति देता है, इसलिए आप njuffa के उत्तर के C संस्करण को लागू कर सकते हैं कि मैं केवल थोड़ा सा स्थानांतरण और जोड़ने का उपयोग करके कैसे गुणा और भाग कर सकता हूं? जो भागफल और शेष उत्पादन करता है। चूंकि आपके पास गैर-संतृप्त जोड़ है, आप रैपिंग ऐड को लागू कर सकते हैं (और फिर रैपराउंड की जांच करके मैनुअल कैरी-आउट डिटेक्शन कर सकते हैं, जैसा कि नाथन सी में करता है।)

joddआपको कम बिट का परीक्षण करने देता है, जैसे if (x&1), जो आपको मानक गुणा एल्गोरिथ्म को भी लागू करने देगा। इसलिए यदि आपके पास एक विभाजन एल्गोरिथ्म है जो केवल आपको एक भागफल देता है, तो आप remainder = dividend - quotient*divisorलॉग-टाइम के साथ गुणा कर सकते हैं ।