Slashdot Mirror

There is open source code for tons of the traditionally G.7xx CODECs around. The issues many of them require licensing various peoples patents. A casual look at speex would make me think that it is quite likely to infringe someone's CELP patents. Does anyone have any thoughts on this? It's really cool to see something like speex happening but there are a few other things that you might want to think about.

Global IP Sound put out a codec for voice called iLBC. It is specifically designed to avoid infringing known patents. It's sound quality vs. packet loss is very good for IP systems. This is being standardized by the IETF. All the source code is open source and in the draft which you can find at http://www.ietf.org/internet-drafts/draft-ietf-avt -ilbc-codec-00.txt.

Sun has a free implementation of CCITT compression types G.711, G.721 and G.723 at ftp://ftp.cwi.nl/pub/audio/ccitt-adpcm.tar.gz. This is just a free implementation - it does not give you a license to the patents.

Various people including Cisco have been working with the license holders of G.729 IPR to make it available for "pre-commercial" systems, developers, and education. http://www.vovida.org/applications/downloads/G729A /

It is striking that this nonsense FORTRAN debate makes it to the /. front page on the day that the death of E.W.Dijkstra has been announced. It is even more striking that the news about the loss of this computer science giant is deemed of less significance by your moderators. What is next? Advocating the implementation of 'goto' in java 3?

E.W.D. was one of the most influential pioneers of computer science, like Turing, Zuse and Von Neuman. His work was always been in the light of creating a solid mathematical foundation for programming. His most remarkable achievements include the wide acceptance of 'structured programming', the invention of semaphores and ofcourse the Dijkstra shortest-path algortihm. He was awarded the ACM Turing Award in 1972. For /.-ers is may be interesting that he also started the first real flamewar with his infamous "Goto considered harmful"-article.

For the news on his death: here, here or here.

For programmers who like to read all of his manuscripts (if you haven't read them, you don't know what programming is about): there is a great archive of all his material. Dijkstra died at the age of 72. May he rest in peace and may his work live on.

Back on topic:

FORTRAN, "the infantile disorder", by now nearly 20 years old, is hopelessly inadequate for whatever computer application you have in mind today: it is too clumsy, too risky, and too expensive to use.
-- Edsger W. Dijkstra.

My router (Netgear RT314) has a telnet screen that displays through (Tx & Rx). I haven't checked with my new 1184/160 G.Lite DSL connection, but with my old Nortel (unknown standard) 960/120 I saw this problem. When I was downloading at full speed (105kB/s), I saw 3-4kB/s upstream activity, which was in excess of 20% of the upstream bandwidth. No wonder that fast uploads choked concurrent downloads. I increased my RWIN, but I don't want it above 32K. Unfortunately, this didn't have much affect.

I think the situation is made worse when the DSL line is set for interleave rather than fast path. On my line, the first hop latency with interleave path is about 70ms, and fast path it is about 10-15ms. I know this because my telco recently tried to switch me over to fast path, which resulted in 40% packet loss due to a higher communication error rates with the modem and the other end (DSLAM port?) at the CO.

This excellent paper (PostScript format) describes some of this, and in particular, interleave path vs. fast path.

Theres only one True tetris in my eyes, the 1989 IOCCC Best Game winner, A true classic.

of course, it has been cleaned up and improved, and is now included as tetris-bsd in the BSD games collection.

There is no competing P2P software on the Macintosh. MacPython is mature. Announce your port on www.macintouch.com. Instant 5% of all computer users.

A mere 371 bits suffice to encode a universal combinator equivalent to ...(a) universal Turing machine:

11100110010100110010110011000010001110010101110010 110
01100101001100101100101001100101100101011100110010 100
01101110011001100110001011010110100101011100101011 100
10110011001010011000010001110011001010010010100101 100
01110001011100110000100011011100110010100110010110 010
10011001011001010111001100101000110111001100010110 110
00110111001100101001100110010100110000100011000110 001

Dan Brumleve has a written a combinator interpreter in Perl that may be capable of evaluating Tromp's strange machine.

A mere 371 bits suffice to encode a universal combinator equivalent to ...(a) universal Turing machine:

11100110010100110010110011000010001110010101110010 110
01100101001100101100101001100101100101011100110010 100
01101110011001100110001011010110100101011100101011 100
10110011001010011000010001110011001010010010100101 100
01110001011100110000100011011100110010100110010110 010
10011001011001010111001100101000110111001100010110 110
00110111001100101001100110010100110000100011000110 001

Dan Brumleve has a written a combinator interpreter in Perl that may be capable of evaluating Tromp's strange machine.

A mere 371 bits suffice to encode a universal combinator equivalent to ...(a) universal Turing machine:

11100110010100110010110011000010001110010101110010 110
01100101001100101100101001100101100101011100110010 100
01101110011001100110001011010110100101011100101011 100
10110011001010011000010001110011001010010010100101 100
01110001011100110000100011011100110010100110010110 010
10011001011001010111001100101000110111001100010110 110
00110111001100101001100110010100110000100011000110 001

Dan Brumleve has a written a combinator interpreter in Perl that may be capable of evaluating Tromp's strange machine.

CWI has several source code license agreements with companies in The Netherlands, USA, Germany and France which allow them to use the Number Field Sieve factorization code as this was and is being developed by P.L. Montgomery, A.K. Lenstra, M. Elkenbracht-Huizing, S. Cavallar and B. Dodson. On a non-commercial basis, the NFS source code has also been made available for research purposes to other cooperating groups. A group of the Royal Institute of Technology in Stockholm (Hastad) has used this code as a basis for factoring a hard 512-bit challenge number in October 2000.

CWI has several source code license agreements with companies in The Netherlands, USA, Germany and France which allow them to use the Number Field Sieve factorization code as this was and is being developed by P.L. Montgomery, A.K. Lenstra, M. Elkenbracht-Huizing, S. Cavallar and B. Dodson. On a non-commercial basis, the NFS source code has also been made available for research purposes to other cooperating groups. A group of the Royal Institute of Technology in Stockholm (Hastad) has used this code as a basis for factoring a hard 512-bit challenge number in October 2000.

The current record factorings were done with the GNFS (General Number Field Sieve).

GNFS consists of a sieving phase that searches a fixed set of prime numbers for candidates that have a particular algebraic relationship, modulo the number to be factored. This is followed by a matrix solving phase that creates a large matrix from the candidate values, then solves it to determine the factors.

The sieving phase may be done in distributed fashion, on a large number of processors simultaneously. The matrix solving phase requires massive amounts of storage and is typically performed on a large supercomputer.

Some pointers:

• Integer factorization
• RSA-155 English press release
• Description of the task, from Singh's The Codebook Challenge
• RSA-129 factoring
• What are the best factoring methods in use today? (RSA Security FAQ)
• A Cost-Based Security Analysis of Symmetric and Asymmetric Key Lengths by Bob Silverman

In case you haven't noticed...It isn't easy, and cannot be fully solved using a distributed.net technique.

to factor a 760-bit number in one year would require 215,000 Pentium-class machines, each with 4 Gigabytes of physical RAM.

to factor a 1620-bit number in one year would require 1.6 x 10^15 Pentium-class machines, each with 120 Terrabytes of physical RAM.

Good luck.

Hi,
I suggest a very (very) old game coming from China, the Game of Go. Whereas chess is a battle (you have to kill the King), Go is a war (you have to conquer territory, battles are a mean, not a goal).
Like chess, Go is spacelly limited, but the number of possible games is incredibily huge (something around 10^600).
When a weak player meets a strong player, this one can have a handicap : this means the game won't be so easy for the strong one, and not so difficult for the weaker one : so everyone is happy to play.
Although rules are really simple, the game in itself can be very very complex : then the goal may not be to win, but to do a nice game, an elegant game.
For more informations, have a look at :
The Internet Go Server, to play online ;
this page to have a nice introducton.
Final word : Go is around 3500 years old.

Some information

Friends, I urge you to check out the lambda calculus or combinatory logic . Both of these are simpler (IMO), complete, and are a good complement to turing machines for certain kinds of problems. Here's combinatory logic, for instance:

K a b => a
S a b c => a c (b c)

That's it. All computable functions can be built out of Ss and Ks defined this way... holy mindfuck, Batman!

Well, I tried to paste it, but couldn't get it to work out in fixed-width font. The link to the author is here, and he explains how he came up with it.

Very interesting reading on maze theory.

Other resource for information on AS3AP:

http://www.cwi.nl/~kwakkel/pythagoras/testpilot/ Da.html#REF80734

It searches sector-by-sector to find the locations of partitions. You can usually feed the output back into sfdisk to recreate them.

It works good, saved my butt :-)

Chess is a fine game though I find the rules to be a little ad hoc and for me this makes the game less than elegant. Go, on the other hand, has a tiny set of very elegant and natural rules and yet it has some of the richest gameplay that can be found on a board. For those who haven't met the game yet it's played with a large rectangular grid. Players take turns in placing stones of their colour (black or white) one by one on the board. Two neighbouring stones are considered to be connected. A connected group is an army. Free grid points adjacent to an army are called liberties. An army with no liberties is considered captured and is taken from the board. That's basically all there is to it - the rest are details. It appeals to a lot mathematicians because of the topological nature of the rules! It's the national board game of Japan with a big following there. It seems less well known in the US which is a great pity. Another cool thing about Go is that in a few days a human get up to the standard that computers are at. It's an amazing challenge to write a good Go program! I had a quick look for links with introductions. This seems OK. For obvious reasons it's quite hard to do a good web search for information about Go.

hm...
at my work (CWI) we used to use (and still have) NTrigue from Insignia.
We use it to have people on SGI's and SUN's log in to our NTrigue server, where they are able to run NT 3.5 apps...
MicroSoft stopped the development by Insignia, so unfortunately there is no NT4 version :(

When you run NTtrigue you get your own dedicated NT display, unlike VNC...

--
Dutch Linux Users Group

One lesson GvR took away from ABC was the importance of OS interfaces; in ABC you couldn't walk through directories or open files, though it provided persistent variable storage that was an abstraction on top of files. This made ABC a nice sandbox to play in, but you couldn't get out of it, and ultimately this proved too confining.

More info is here from CWI. It took them between 3.5 ad 3.7 months (I've seen both numbers). But here's the stats on what the used:

"Sieving was done on about 160 175-400 MHz SGI and Sun workstations, on 8 300 MHz SGI Origin 2000 processors, on about 120 300-450 MHz Pentium II PCs, and on 4 500 MHz Digital/Compaq boxes. The total amount of CPU-time spent on sieving was 35.7 CPU years estimated to be equivalent to approximately 8000 mips years. Calendar time for sieving was 3 1/2 months."

"(L: using lattice sieving code from Arjen K. Lenstra C: using line sieving code from CWI)

20.1 % (3057 CPU days) Alec Muffett (L at Sun Microsystems Professional Services, Camberley, UK)
17.5 % (2092 CPU days) Paul Leyland (L,C at Microsoft, Cambridge, UK)
14.6 % (1819) Peter L. Montgomery, Stefania Cavallar (C,L at CWI, Amsterdam)
13.6 % (2222) Bruce Dodson (L,C at Lehigh University, Bethlehem, PA, USA)
13.0 % (1801) Francois Morain and Gerard Guillerm (L,C at Ecole Polytechnique, Palaiseau, France)
6.4 % (576) Joel Marchand (L,C at Ecole Polytechnique/CNRS, Palaiseau, France)
5.0 % (737) Arjen K. Lenstra (L at Citibank, Parsippany, NJ, USA and Univ. of Sydney, Australia)
4.5 % (252) Paul Zimmermann (C at Inria Lorraine and Loria, Nancy, France)
4.0 % (366) Jeff Gilchrist (L at Entrust Technologies Ltd., Ottawa, Canada)
0.65 % (62) Karen Aardal (L at Utrecht University, The Netherlands)
0.56 % (47) Chris and Craig Putnam (L at ?)

Calendar time for the sieving was 3.7 months.
The relations were collected at CWI and required 3.7 Gbytes of disk space."

Quoted material from the link provided at the begining.