Re: Number of 1's in 64 bit number...[don't read if not interestedin algos/math...]
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
Reply to: