🧑🏿‍🤝‍🧑🏿 🤩 ➖ सबसे छोटा दशमलव कार्यक्रम 🍬 ⛓️ 👨🏿‍🚀

1984 में, स्टीवन लेवी की पंथ पुस्तक, हैकर्स: हीरोज ऑफ द कंप्यूटर रिवोल्यूशन , का विमोचन किया गया। एक रूसी रूसी अनुवाद है, लेकिन यह आदर्श से बहुत दूर है। मैंने इसमें अशुद्धियों को ठीक करने का बीड़ा उठाया, इसके बगल में अंग्रेजी मूल को रखा (वैसे, और यह पाप के बिना नहीं है), लेकिन दूसरे अध्याय के बाद इसे छोड़ दिया। एक तरह से या किसी अन्य, मैं आपके ध्यान को एक दशमलव प्रणाली में एक संख्या को प्रिंट करने के लिए सबरूटिन को समर्पित एक अलग लेख में पढ़ सकता हूं (आप इसे एक अलग लेख में पढ़ सकते हैं )। ऐसे कार्यक्रम को कितना कम किया जा सकता है? सीमा क्या है?

अगस्त 2018 में, मैंने सोवियत प्रोसेसर 1801BM1 के निर्देशों के सटीक निष्पादन समय को मापने के लिए एक कार्यक्रम लिखा था (इसमें पीडीपी -11 निर्देशों का एक सेट है )। बीके 0011M कंप्यूटर के लिए " अच्छा Apple " डेमो पर काम करते समय सटीक समय (प्रोसेसर चक्र में) जानना आवश्यक था । मैं दशमलव में माप परिणाम देखना चाहता था। ऐसा करने के लिए, मुझे अपनी खुद की सबरूटीन लिखनी थी - परीक्षण की बारीकियों के कारण सिस्टम फ़ंक्शन उपलब्ध नहीं थे।

पहली चीज़ जो मैंने की थी, वह 10 की शक्तियों के साथ एक TEN सरणी थी। प्रक्रिया रजिस्टर R0 में एक संख्या लेती है, आउटपुट NUMBER पर एक पाठ स्ट्रिंग है। महत्वपूर्ण: प्रोसेसर में कोई विभाजन निर्देश नहीं है !

	MOV #NUMBER,R1	; pointer to output text string
	MOV #TEN,R5
1:	CMP (R5)+,R0 	; skip leading zeros
	BHI 1		; branch if higher, for 16-bit not signed
	MOV -(R5),R3
	BEQ 4		; if less then 10

2:	MOV #47.,R4	; 0 symbol in ASCII codepage - 1
3:	INC R4		; count digits
	SUB R3,R0
	BHIS 3		; branch if higher or same, for 16-bit not signed
	MOVB R4,(R1)+	; print R4

	ADD (R5)+,R0
	MOV (R5),R3
	BNE 2

4:	ADD #48.,R0	; 0 symbol in ASCII codepage
	MOVB R0,(R1)+	; print R0
	CLRB (R1) 	; end of text marker
	RET

TEN:	.WORD 10000.,1000.,100.,10.,0

पीडीपी -11 कोडांतरक को समझने के लिए, यह याद रखना पर्याप्त है कि तर्कों को बाएं से दाएं (पहले स्रोत, फिर रिसीवर) लिखा जाता है, और सशर्त शाखा कमांड बी अक्षर (शब्द शाखा - शाखा) से शुरू होते हैं। मैं एल्गोरिथ्म का वर्णन नहीं करूंगा, यह कोई दिलचस्पी नहीं है और यहां केवल एक प्रारंभिक बिंदु के रूप में दिया गया है। इस दिनचर्या का आकार 22 शब्द है (डेटा सहित नहीं)।

सब कुछ काम करने के बाद, मुझे अचानक स्टीफन लेवी की किताब से कहानी याद आई: हैकर्स एक समान कार्यक्रम के आकार को कम करने के लिए संघर्ष करते थे, और पीडीपी वास्तुकला पर भी। सच है, उनके पास पीडीपी -1 था, लेकिन कुछ साल बाद उन्हें पीडीपी -11 मिला।

किताब खोलते हुए, मुझे एक बेहद अस्पष्ट वर्णन मिला। MIT के हैकरों ने शुरू कियाबस मुझे दशमलव स्थानों की सूची से पसंद है। लेकिन आगे क्या हुआ यह पाठ से स्पष्ट नहीं है। जाहिर है, यह या तो पुस्तक के लेखक के लिए स्पष्ट नहीं था, उसने बस उस हैकिंग प्रतियोगिता के चश्मदीदों के होंठों से आम शब्द लिख दिए।

मुझे पीडीपी -1 के कार्यक्रमों के इंटरनेट संग्रह में तल्लीन करना था । बहुत सारी दिलचस्प चीजें हैं: मिंस्काइट्रॉन, मुंचिंग वर्ग और अन्य तथाकथित "डिस्प्ले हैक्स" (वैसे, यह पहले से ही तब तक उल्लेखनीय है - 60 के दशक की शुरुआत में - एमआईटी हैकर्स ने " डेमो " शब्द का उपयोग उसी अर्थ में किया था जिसमें हम अब इसका उपयोग करते हैं) डिमोसिन पर)। संग्रह में कई सिस्टम रूटीन हैं, लेकिन, दुर्भाग्य से, उनके बीच कोई दशमलव संख्या नहीं है।

फिर, एक डिबगर के साथ सशस्त्र, मैंने यह देखने का फैसला किया कि यह प्रक्रिया एमकेडीओएस ऑपरेटिंग सिस्टम में कैसे लागू की गई थी, जिसका उपयोग मैं बीके 0010 और बीके 0011 एम पर करता हूं। अरे चमत्कार! - बारीकी से देखने पर, मुझे एहसास हुआ कि पुस्तक "हैकर्स" से धूमिल वर्णन के साथ उपप्रोग्राम बहुत अच्छी तरह से फिट बैठता है। यहाँ उसका कोड है:

	MOV #10.,R4
	CLR R2
1:	CLR R1
2:	SUB R4,R0 	;    10,    
	BLO 3
	INC R1 		;  -   
	BR 2
3:	ADD R4,R0
	ADD #48.,R0 	; ASCII-  0
	INC R2		;  -   
	MOVB R0,-(SP)
	MOV R1,R0 	;    -   
	BNE 1
	INC R2
	MOVB #32.,-(SP)	; ASCII- 
4:	MOVB (SP)+,R0
	CALL PRINT
	SOB R2,4	;     
	RET

कार्यक्रम स्टैक पर एक पाठ स्ट्रिंग बनाता है, फिर प्रत्येक सहेजे गए वर्ण के लिए प्रिंट प्रक्रिया को कॉल करता है। जाहिरा तौर पर, यह बिल्कुल स्टीफन लेवी की पुस्तक में था, जो वाक्यांश के तहत था "विपरीत तरीके से धर्मान्तरित, और एक चालाक सॉफ्टवेयर की मदद से यह सही क्रम में प्रिंट करता है।" कोड पर टिप्पणियों से एल्गोरिथ्म की अन्य विशेषताएं स्पष्ट होनी चाहिए।

सबरूटीन का आकार 23 शब्द है , लेकिन आप इसकी तुलना सीधे मेरे सबरूटीन से नहीं कर सकते: परिस्थितियां बहुत अलग हैं। मैंने अपनी स्थितियों में MKDOS से कार्यक्रम का रीमेक करने का फैसला किया: स्मृति में एक पाठ स्ट्रिंग का गठन।

अंत में, मैंने महसूस किया कि नंबर 10 को घटाने का केवल विचार छोड़ना बेहतर है, और बाकी को खरोंच से लिखना। ~~संसार~~ अनुकूलन के कई अंतराल के बाद , मुझे निम्नलिखित मिला:

	MOV #NUMBER,R1	; pointer to output text string
	CLRB -(R1)	; end of text marker
	MOV #10.,R4
1:	MOV #-1.,R5
2:	INC R5		; counter of 10s
	SUB R4,R0
	BHIS 2		; branch if higher or same
	ADD #58.,R0	; #10. + '0' ASCII code
	MOVB R0,-(R1)	; store R0 to text string
	MOV R5,R0	; let's count next how many 10s in number of 10s
	BNE 1
	RET		; returns text string pointer in R1

16 शब्द , सीमा तक पहुँच गया है (मैंने सोचा), यहाँ यह है - निर्वाण, जिसके बारे में स्टीफन लेवी ने भावनात्मक रूप से लिखा था!

यहाँ क्या तरकीबें लगाई गई हैं:

पहला कमांड पॉइंटर को शुरुआत में नहीं, बल्कि टेक्स्ट लाइन के अंत में सेट करता है। पाठ दाएं से बाएं भरा है - यह भी सुविधाजनक है क्योंकि आउटपुट पर हमें लाइन की शुरुआत का पता मिलता है, जो पाठ मुद्रण प्रक्रिया को भेजे जाने के लिए तैयार है।
, . (INC R5) 1. 0, , ?.. , 10 – , . , . . – . : 1 , , 1 ( ). , , . . -1.
10, , , . – ( ). , – . , , . ( 10 10 ) . : ASCII- 0, ! , , . ADD #58.,R0 (48+10).

मैं इस कार्यक्रम से बहुत खुश था कि मैंने इसे zx-pk.ru फोरम पर साझा करने का फैसला किया (बिना बहस के आलोचना करने के लिए स्थानीय परंपराओं पर कुछ भी संदेह नहीं किया)। समुदाय की प्रतिक्रिया कुछ इस तरह थी: "आपको यह देखना होगा कि उन्होंने डीईसी में यह कैसे किया, यह एक क्लासिक है।"

खैर, यहां DEC से एक कार्यक्रम है , जो कंपनी ने PDP-11 बनाया है और MIT के कुछ हैकर्स को इसके रैंक में शामिल किया है:

; RETURNS:
; R0 = 0
; R1 -> byte following last digit in converted number
CVBTOD:	MOV	R0,-(SP)	;SAVE THE NUMBER PASSED TO US
	CLR	R0		;SET FOR CRUDE DIVIDE BY 10.
10$:	INC	R0		;BUMP QUOTIENT
	SUB	#10.,(SP)	;REDUCE NUMBER BY 10.
	BHIS	10$		;IF SIGN DIDN'T CHANGE...
	ADD	#10.+48.,(SP)	;MAKE REMAINDER PRINTABLE
	DEC	R0		;REDUCE QUOTIENT
	BEQ	20$		;IF ZERO, TIME TO PRINT
	CALL	CVBTOD		;OTHERWISE, RECURSE !
20$:	MOVB	(SP)+,(R1)+	;STORE A CONVERTED DIGIT
	RETURN			;UNWIND THE RECURSION

14 शब्द , अच्छा! या नहीं? मैं हार गया था, लेकिन चलो एक करीब देखो:

वर्ण 0 के ASCII कोड और संख्या 10 को जोड़ना एक ऑपरेशन में किया जाता है। यह पता चलता है कि 70 के दशक में इस तरह की चाल का इस्तेमाल किया गया था। ठंडा।
कार्यक्रम खुद को पुनरावर्ती कहता है - एक सुंदर समाधान!
– , . – .
R1 . , , .
, ! ?.. , . , zx-pk.ru MOV #NUMBER,R1 !

कुल मिलाकर, वास्तविक आकार 16 शब्द है । बिल्कुल मेरी तरह। दोनों कार्यक्रमों में 12 निर्देश शामिल हैं। तो कौन सा बेहतर है?

यहां तक कि अगर आप स्टेक कॉल को रजिस्टर कॉल के साथ बदलते हैं, तो DEC प्रोग्राम लूप के अंदर DEC R0 और CALL निर्देशों के कारण धीमा हो जाएगा।

लेकिन वह सब नहीं है। जब मैंने इस लेख को लिखना शुरू किया, तो मैंने देखा कि मेरे कार्यक्रम में एक अल्पविकसित (MKDOS से) निर्देश MOV # 10., R4 था - इसका आंतरिक लूप को तेज करने के अलावा कोई मतलब नहीं है। उससे छुटकारा पाने का समय आ गया है।

	MOV #NUMBER,R1	; pointer to output text string
	CLRB -(R1)	; end of text marker
1:	MOV #-1.,R5
2:	INC R5		; counter of 10s
	SUB #10.,R0
	BHIS 2		; branch if higher or same
	ADD #58.,R0	; #10. + '0' ASCII code
	MOVB R0,-(R1)	; store R0 to text string
	MOV R5,R0	; let's count next how many 10s in number of 10s
	BNE 1 		; loop if R0 is not zero
	RET		; returns text string pointer in R1

15 शब्द । 11 निर्देश। अब, ऐसा लगता है, यह सब है।

खैर, मेरे अनुकूलन के विचार खत्म हो गए हैं। यह एक प्रेरणादायक था, यहां तक कि एक जुआ, चुनौती। यह उल्लेखनीय है कि PDP-1 के लिए 60 के दशक की शुरुआत में हैकिंग के छात्र द्वारा प्रस्तावित विचार का उपयोग DEC दस और यहां तक कि बीस साल बाद किया गया था, और यह 2000 के दशक तक सोवियत कंप्यूटर BK 0011M पर लागू किया गया था। आश्चर्यजनक रूप से, वर्ष 2018 में, एल्गोरिथ्म को आंशिक रूप से सुदृढ़ और अनुकूलित करना संभव था। चारित्रिक रूप से, कई लोग इसे असंभव मानते थे।

तो, यहाँ पवित्र कंघी बनानेवाले की रेती (स्टीफन लेवी के अनुसार) है, जो 60 के दशक के हैकर्स ने पीडीपी के लिए सबसे छोटा दशमलव कार्यक्रम खोजने की कोशिश की थी। या ... शायद कम भी हो?

अपडेट करें: मुझे पता था कि यह दिन आएगा, लेकिन मैंने इतनी जल्दी नहीं सोचा :) यह पता चला कि कार्यक्रम को एक और शब्द से कम किया जा सकता है! इस विचार को Mr_Rm की टिप्पणियों में सुझाया गया था :

	MOV #NUMBER,R1	; pointer to output text string
	CLRB -(R1)	; end of text marker
1:	CLR R5
2:	INC R5		; counter of 10s +1
	SUB #10.,R0
	BHIS 2		; branch if higher or same
	ADD #58.,R0	; #10. + '0' ASCII code
	MOVB R0,-(R1)	; store R0 to text string
	MOV R5,R0	; let's count how many 10s in number of 10s
	SOB R0,1	; subtract 1 and loop if not zero
	RET		; returns text string pointer in R1

14 शब्द । 11 निर्देश।
चाल यह है। याद रखें, मैंने लिखा है कि R5 चक्र के "गलत" संगठन के साथ, एक को आवश्यकता से अधिक प्राप्त किया जाता है? अच्छा आज्ञा दो! हम इसे कार्यक्रम के अंत में कम कर देंगे। पिछले संस्करण में, R5 को R0 में कॉपी किया गया था, जिसके बाद BNE (शाखा अगर शून्य के बराबर नहीं है) कमांड ने R0 की जाँच की, और यदि यह शून्य के बराबर नहीं है, तो यह चक्र की शुरुआत में चला गया। अगर केवल हम सबसे पहले R0 को एक से कम करेंगे, और फिर (अगर हमें शून्य नहीं मिला) शुरुआत में जाएं ... एक मिनट रुकें, लेकिन यह एक सामान्य SOB (सबट्रेक्ट वन और ब्रांच) चक्र कमांड है। सच है, यहां इसका उपयोग एक विहित तरीके से नहीं किया गया था: यह एक बार पूरा होता है, और फिर चक्र काउंटर को भटका दिया जाता है। यह हतोत्साहित करने वाला लगता है, लेकिन अगर आप उप-संस्करण के पिछले संस्करण को देखें, तो यह स्पष्ट हो जाता है कि इसमें से एक नए को कैसे छोटा किया जाए।

उपयोगी कड़ियाँ:

रूसी में डाउनग्रेड पत्रिका , 28 और 29 को अंक - बीके / पीडीपी पर कोडांतरक ट्रिक्स पर लेख।
2019 में बीसी 0010 के तहत प्रोग्रामिंग आधुनिक विकास साधनों का अवलोकन है।
Pouet.net पोर्टल पर BK 0010 और BK 0011M का प्रदर्शन
डेमोक्रेट की हैकर जड़ें - कैओस कंस्ट्रक्शन 2016 में सेमिनार की रिकॉर्डिंग, 60 के दशक के "डिस्प्ले हैक्स" का विश्लेषण।
हैकर्स: विजार्ड ऑफ़ द इलेक्ट्रॉनिक एज 1984 की एक डॉक्यूमेंट्री है, जो स्टीफन लेवी की एक किताब पर आधारित है।

सबसे छोटा दशमलव कार्यक्रम

More articles: