Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I see this page before. Cracking Playfair code And I download the C file in it.However,I am still confused about the code. How to evaluate a solution? What does this mean?

if (diff > 0 || ((float) rand () / RAND_MAX < exp (diff / T)))
champion = mysquare;

And what is the T and the score?

  K->score = (float) digvalue / N;

  T *= 0.98;

Thanks for your help!I am really urgent to know this.

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

I didn't look at the rest of the code, but this looks like simulated annealing. T is a temperature parameter that regulates the randomness you allow in the search. The lower T gets, the less likely it is that a step that increases the energy (the function to be minimized) is accepted. The if statement implements the Metropolis algorithm for bringing the system into statistical equilibrium at temperature T.

[Edit in response to the comments:]

There's more stuff in the directory containing the source code, including the input file for digstat (distat.log) and a short explanation (playn.txt) (which by the way would have told you that the code performs simulated annealing). On comparing the input file for digstat with other digram frequency data, it looks like these are natural logarithms of scaled digram frequencies, rounded to integers. (The scaling has no effect on the algorithm since it merely adds a constant to all scores.)

The code you quote computes the part of the Kullback–Leibler divergence that depends on the current key. This is the relative entropy between the digram frequencies corresponding to the current key and the actual English diagram frequencies. The part $\sum p_i\log p_i$ that involves only the actual digram frequencies and doesn't depend on the digram frequencies corresponding to the current key is omitted, since it would cancel out in the energy differences used in the Metropolis algorithm.

share|improve this answer
    
Wow!!!I am dazzled by it!I know little about this!Thanks!And what about the variable " int digstat[25][25]; "?It is commented that /* log digram frequency table */ . If it is the log of the frequency,why it is declared to be int? –  furskytl Oct 6 '11 at 7:36
    
Excuse me!Can you look at the code in detail and explain why is this: for (i = 0; i < 25; i++) for (j = 0; j < 25; j++) { n = dfreq[i][j]; if (n) { digvalue += n * digstat[i][j]; dfreq[i][j] = 0; } } K->score = (float) digvalue / N; And what is in the digstat[][]?Thanks! –  furskytl Oct 6 '11 at 13:57
    
@furskytl: OK, I've added something on that to the answer. –  joriki Oct 7 '11 at 8:25
    
Thanks very much!Thanks!With your help,I am acquainted with a great deal of useful knowledge!Thanks again! –  furskytl Oct 7 '11 at 11:50
    
You're welcome :-) –  joriki Oct 7 '11 at 12:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.