*To*: debian-user@lists.debian.org*Subject*: Re: Number of 1's in 64 bit number...[don't read if not interestedin algos/math...]*From*: DSC Siltec <dscpubl@siltec.lt>*Date*: Fri, 26 Apr 2002 09:32:31 +0200*Message-id*: <[🔎] 3CC9028F.226E5F@siltec.lt>*References*: <Pine.LNX.4.44.0204251313340.9662-100000@dberlin.org>

How about some NASM code? (I don't know NASM, so I'll just have to write this in assembler...) ; ; ; Assume that the 64-bit number is stored at EDS:ESI PUSH EAX ; Only if we need to save AX (usually not). PUSH ESI ; Only if we need to save ESI (probably not) PUSH EDS ; Save our data segement PUSH EBP ; Save our base pointer 66: LODSB ; Code 66, if I remember, is SHORT-OPERAND PUSH EAX ; So this loads AL, and increments ESI 66: LODSB ; by 1. We then store the operand PUSH EAX ; We do this four times. 66: LODSB PUSH EAX 66: LODSB PUSH EAX PUSH ECS ; Change EDS to Code segment POP EDS MOV EBP,#DATA ; Load Base pointer with data area POP ESI MOV EAX,[EBP+ESI] ; four times we get or add whatever POP ESI ; our table lookup yields. ADD EAX,[EBP+ESI] POP ESI ADD EAX,[EBP+ESI] POP ESI ADD EAX,[EBP+ESI] POP EBP POP EDS POP ESI POP EAX ; Either Return from subroutine here, or continue with ; program. [DATA] DB 00 00 00 00 01 00 00 00 01 00 00 00 02 00 00 00 DB 01 00 00 00 02 00 00 00 02 00 00 00 03 00 00 00 ; Start = 00000xxx ; ; For shorthand, I am writing the rest of the list as just 1-byte, ; but the list should be stored as 4-byte words, as above for best speed. ; That is the difference between my "DB -- Data byte" and ; "EW -- Extended word". ; ; EW 01 02 02 03 02 03 03 04 ; Start = 00001xxx EW 01 02 02 03 02 03 03 04 ; Start = 00010xxx EW 02 03 03 04 03 04 04 05 ; Start = 00011xxx EW 01 02 02 03 02 03 03 04 ; Start = 00100xxx EW 02 03 03 04 03 04 04 05 ; Start = 00101xxx EW 03 04 04 05 04 05 05 06 ; Start = 00111xxx EW 01 02 02 03 02 03 03 04 ; Start = 01000xxx EW 02 03 03 04 03 04 04 05 ; Start = 01001xxx EW 02 03 03 04 03 04 04 05 ; Start = 01010xxx EW 03 04 04 05 04 05 05 06 ; Start = 01011xxx EW 02 03 03 04 03 04 04 05 ; Start = 01100xxx EW 03 04 04 05 04 05 05 06 ; Start = 01101xxx EW 03 04 04 05 04 05 05 06 ; Start = 01110xxx EW 04 05 05 06 05 06 06 07 ; Start = 01111xxx EW 01 02 02 03 02 03 03 04 ; Start = 10000xxx EW 01 02 02 03 02 03 03 04 ; Start = 10000xxx EW 02 03 03 04 03 04 04 05 ; Start = 10001xxx EW 02 03 03 04 03 04 04 05 ; Start = 10010xxx EW 03 04 04 05 04 05 05 06 ; Start = 10011xxx EW 02 03 03 04 03 04 04 05 ; Start = 10100xxx EW 03 04 04 05 04 05 05 06 ; Start = 10101xxx EW 04 05 05 06 05 06 06 07 ; Start = 10111xxx EW 02 03 03 04 03 04 04 05 ; Start = 11000xxx EW 03 04 04 05 04 05 05 06 ; Start = 11001xxx EW 03 04 04 05 04 05 05 06 ; Start = 11010xxx EW 04 05 05 06 05 06 06 07 ; Start = 11011xxx EW 03 04 04 05 04 05 05 06 ; Start = 11100xxx EW 04 05 05 06 05 06 06 07 ; Start = 11101xxx EW 04 05 05 06 05 06 06 07 ; Start = 11110xxx EW 05 06 06 07 06 07 07 08 ; Start = 11111xxx Now for my own Algorithm challenges: I figured out how perform a Discrete Fourier Transform with about 80% of the multiplications of a standard Fast Fourier Transform (see Numerical Recipes www.nr.com ... although their routine takes 400% longer than a good standard FFT for demonstration purposes.) Also with only 50% of the looping. I'm probably not the first to figure this one out, but it is an interesting challenge. Hint: View the square matrix W vectorally in the complex plane, and then look at what is going on. Now view the FFT's compressed matrix W', and see what is going on there. Now optimize. Can anybody figure that one out? 2: Assembly language, No Math Coprocessor, No multiply. Algorithm for fast logarithm. (Hint: Log-base-2, table lookup) Algorithm for fast square root (Hint: about as fast as a divide) 3: Optimal card sorting algorithm for a computer. What is the minimum number of comparisons you can get? (hint: it approaches the standard entropy limit log-2(N) ). (4) 3-D visualization algorithms: If you have N photos of an object, and identify P points, and you want to determine where each camera was when it took the shot [assume you have high quality lenses with no aberration]... What is the minimum number of photos required? What is the minimum number of points required? And for each, what is the other value if you minimize the one? (5) RSA - breaking. Identify an analog algorithm for the fast generation of all primes and only primes. Hint: imagine a broken triangular wave function, and a single triangular wave function __ ___ ___ ___ ___ ___ \/ \/ \/ \/ \/ \ _______/\__________________ Now add the two. __ ________ ___ ___ ___ ___ \/ \/ \/ \/ \/ \ Now use an analog algorithm (or these days, the Parker - Souchacki variation of the Picard iteration) to generate a function that looks like this or a variation of. Now use the Parker - Souchacki algorithm or your analog variant to define that whereever the algorithm is 1, it generates another function from that point, and the function as a recursive multiplication of all such functions. That will give you a primes - only function. Each of the first 4 has a specific answer. I am sure of the answers for 1-4. I am pretty sure that an answer exists to #5, but have not had the time to develop the Parker Souchacki algorithms. [ Now consider that the NSA somehow convinced the inventor of PGP that his compliance didn't matter... and so therfore he should comply -- and he did, leaving as his public statement that no encryption is unbreakable. ] - Mike -- To UNSUBSCRIBE, email to debian-user-request@lists.debian.org with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org

- Prev by Date:
**Re: docbook: xml -> (x)html conversion** - Next by Date:
**Also from Algorithm genius** - Previous by thread:
**Re: fetchmail daemon dies, won't restart** - Next by thread:
**Also from Algorithm genius** - Index(es):