text:
Prime sieve and sort (x86 asm)
Your challenge is to write a routine, in x86 assembly, which takes a buffer containing 32-bit signed integers and writes a sorted list of the prime values to another buffer, then returns the number of values written to the output buffer. The winning solution is the one that uses the least instructions.
Here's a pseudo-C example of the process:
int __stdcall SortedPrimes(DWORD* input, DWORD* output)
{
    int ctr_in = 0;
    int ctr_out = 0;
    int val = 0;
    // copy primes to output buffer
    while((val = input[ctr_in]) != 0)
    {
        ctr_in++;
        if(isPrime(val))
            output[ctr_out++] = val;
    }
    // you must implement this sort, too!
    sort(output);
    return ctr_out;
}

// for testing/illustration purposes only
// you don't need to implement this part!
void test()
{
    int count = 0;
    int i = 0;
    int v = 0;

    // allocate buffers
    DWORD* input = (DWORD*)calloc(1024, sizeof(DWORD));
    DWORD* output = (DWORD*)calloc(1024, sizeof(DWORD));

    // fill input buffer with data
    input[0] = 0x12345678;
    input[1] = 0x57AC0F10;
    ...
    input[1022] = 0x13371337;
    input[1023] = 0; // terminating value is zero!

    // invoke your function! :]
    count = SortedPrimes(input, output);

    // dump output
    printf("Found %n primes.\n", count);
    while((v = output[i++]) != 0)
        printf("0x%x\n", v);

    free(input);
    free(output);
}

Rules:

Assume a modern Intel CPU (e.g. Core i3) running in x86-32 mode.
Assume __stdcall, i.e. parameters pushed from right to left, esp+4 is a pointer to input, esp+8 is a pointer to output, callee is responsible for cleaning stack.
You cannot call any APIs or library functions - the solution must be in pure assembly.
The input buffer consists of 32-bit non-zero signed integers, followed by 0x00000000.
The output buffer is allocated and zero'd before being passed to the function, and its size is the same as the input buffer.
Assume there are no negative inputs, i.e. the range is 0x00000001 to 0x7FFFFFFF.
The sort must be lowest to highest, such that output[0] is the lowest value in the list.
Must give an empty output buffer when given an empty input buffer.
Must properly handle cases where all values are prime / no values are prime.
You may not use compiler macros.
The code must be able to process 1000 inputs in 60 seconds or less.
I'll accept answers in AT&T syntax, but I'd prefer Intel syntax for uniformity.
Winner is the code that has the least number of instructions (i.e. lowest number of lines of code), not the least number of characters.

Assembly is pretty terse, so please add comments to your code where necessary.
Enjoy :)

If there are two or more input values that are equal and prime, should the value be output once or repeated for each occurrence in the input? e.g. if input = {3, 3, 3, 3, 3} should output be: {3} or {3, 3, 3, 3, 3}

Keith Randall brought up a good point in the comments, do we need to preserve the values of ebx,esi,edi at return to comply with the stdcall convention? I'll assume we do unless you want to relax that requirement.

Skizz - either way is fine. Sir_Lagsalot - Yes, they have to be preserved by the callee, as per stdcall.

@Polynomial Is the program permitted to alter the input buffer? The function signature suggests that it is.

@breadbox Sure, why not? :)

26 instructions
I found this task for the first time only yesterday.  sigh.
I took @Sir_Lagsalot's code and removed one xchg.  The changes are too significant for a comment, so I've placed it here for review.
    pushad
    mov     ecx, -1              ; will zero output count and position using next instruction
count_prime:
    inc     ecx                  ; increment output & count if prime
    mov     esi, [esp + 8+32]    ; load output array
find_smallest:
    mov     eax,-3               ; 0xfffffffd is larger than any valid input
    mov     edi, [esp + 4+32]    ; load input array
    db      3dh, 50h             ; mask next instruction on first pass
find_smallest_loop2:
    xchg    eax,[edi-4]          ; swap ecx with values that are smaller, values
                                 ; get replaced with 0xfffffffd as they are used
find_smallest_loop:
    scasd
    jbe     find_smallest_loop
    mov     ebx,1                ; ebx is divisor, will start it at 2 later
                                 ; but we need 1 right now
    cmp     [edi-4],ebx
    je      find_smallest        ; skip inputs of 1
    ja      find_smallest_loop2  ; exit loop if a 0 is reached
    mov     [esi+ecx*4],eax      ; store value in next output position
test_next_divisor:               ; primality test
    mov     eax,[esi+ecx*4]
    cdq
    inc     ebx                  ; 2+
    idiv    ebx                  ; use signed division
    cmp     eax,ebx
    jb      count_prime
    test    edx,edx
    jz      find_smallest
    jns     test_next_divisor    ; exit if remainder is negative
exit_function:
    mov     [esp+28],ecx         ; move count to eax position
    popad
    ret 8

Nice optimisation there :)

32 30 29 28 27 Instructions
Changed my algorithm so we're not all trying to implement the same thing, and it's a little smaller than my earlier attempt. The code repeatedly searches through the input array, finding the smallest value, and replacing it with 0xfffffffd. It then tests if the found value is prime and outputs it if so. The code exits when the input has been completely replaced with 0xfffffffd.
    pushad
    mov     ecx, 0              ; zero output count and position
    mov     esi, [esp + 8+32]   ; load output array
find_smallest:
    mov     eax,-3              ; 0xfffffffd is larger than any valid input
    mov     edi, [esp + 4+32]   ; load input array
find_smallest_loop:
    scasd
    jbe     find_smallest_loop
    xchg    eax,[edi-4]          ; swap ecx with values that are smaller, values
                                 ; get replaced with 0xfffffffd as they are used
    cmp     eax,1
    je      find_smallest        ; skip inputs of 1
    ja      find_smallest_loop   ; exit loop if a 0 is reached
    xchg    eax,[edi-4]          ; swap 0 with lowest value found
    mov     [esi+ecx*4],eax      ; store value in next output position
    mov     ebx,2                ; ebx is divisor, start it at 2
test_next_divisor:               ; primality test
    mov     eax,[esi+ecx*4]
    cdq
    idiv    ebx                  ; use signed division
    cmp     eax,ebx
    cmovb   edx,[edi-4]          ; zero edx if prime to exit loop later on
    adc     ecx,0                ; increment output & count if prime
    inc     ebx
    test    edx,edx
    jz      find_smallest
    jns     test_next_divisor    ; exit if remainder is negative
exit_function:
    mov     [esp+28],ecx         ; move count to eax position
    popad
    ret 8

ebx,esi,edi are callee-save. (I'm assuming we have to adhere to stdcall in this regard.)

Good point, I've updated the code to fix that.

41 29 instructions
The code itself, NASM syntax:
global primes
    section .code
primes:
    pushad
    mov     esi, [esp + 32 + 4]
    mov     dword [esp + 28], 0 ; primes counter
read:
    add     esi, 4
    mov     ecx, [esi - 4]
    jecxz   return          ; zero terminator
    cmp     ecx, 1
    je      read            ; omit 1
    mov     ebx, 2          ; initial divisor
try_divisor:
    mov     eax, ecx        ; get original number from ecx
    mov     edx, 0
    div     ebx             ; divide
    cmp     ebx, eax
    jg      save            ; divisor exceeds sqrt(n), so n is prime
    cmp     edx, 0
    je      read            ; not prime
    inc     ebx             ; next divisor
    jmp     try_divisor
save:                        ; prime number to store is in ecx
    inc     dword [esp + 28] ; increase prime counter
    mov     edi, [esp + 32 + 8]
bubble:                     ; insert prime into output array
    add     edi, 4
    xchg    ecx, [edi - 4]
    jecxz   read
    cmp     ecx, [edi - 4]
    jge     bubble
    xchg    ecx, [edi - 4]
    jmp     bubble
return:
    popad
    ret     8

I borrowed a lot from Keith Randall's solution, but improved prime saving code. So, I guess, my code should be out of competition since it's not completely mine.

ebx,esi,edi are callee-save.  (I'm assuming we have to adhere to stdcall in this regard.)

@KeithRandall That's correct. All general purpose registers, stack registers, etc. must be preserved by the callee, as per stdcall spec.

The value '9' passes your prime check.

You're right, guys, thanks. Will fix tomorrow.

Fixed. Actually, improved Keith Randall's solution.

Doesn't this require that the output array is initialized to all zero?

@KeithRandall Yes, and it's stated in the problem definition: "The output buffer is allocated and zero'd before being passed to the function".

35 31 instructions
        .globl  _primesort
_primesort:
        pushal
        mov     36(%esp),%esi           # load input ptr
        mov     40(%esp),%edi           # load output ptr
        movl    $0,28(%esp)             # count primes in saved eax slot
inputloop:
        add     $4,%esi
        cmp     $1,-4(%esi)
        jl      return                  # 0 = input end marker
        je      inputloop               # special case for 1
        mov     $2,%ecx                 # trial divisor
testloop:
        mov     -4(%esi),%eax
        mov     $0,%edx
        div     %ecx
        cmp     %ecx,%eax
        jl      saveprime               # n/d < d => d > sqrt(n) => no more trial division
        cmp     $0,%edx
        je      inputloop               # found a divisor
        inc     %ecx                    # next trial divisor
        jmp     testloop
saveprime:
        mov     -4(%esi),%eax           # prime
        mov     28(%esp),%ecx           # index of new last element
        jecxz   storeprime              # at start of output array, just store it
bubbledown:
        cmp     %eax,-4(%edi,%ecx,4)
        jl      storeprime              # found spot to store it
        mov     -4(%edi,%ecx,4),%edx
        mov     %edx,(%edi,%ecx,4)      # move larger element up one
        loop    bubbledown              # repeat until start of output array
storeprime:
        mov     %eax,(%edi,%ecx,4)
        incl    28(%esp)
        jmp     inputloop
return:
        popal
        ret

This code is AT&T syntax, and it uses cdecl instead of stdcall, but I think the only difference for the latter would be to replace the ret with ret 0x8.

With 1000 inputs it runs much longer than 60 seconds on my Core 2 Duo.

Ok, fixed.  I now only test up to sqrt(n) before declaring a value prime.  Takes 1/2 second for 1000 instances of 0x7fffffff.

28 instructions
Build with nasm -f elf32:
BITS 32
GLOBAL sortedprimes

;; int sortedprimes(int const *input, int *output)
;; Read a zero-terminated list of numbers from input. Copy only the prime
;; numbers to the buffer output, returning the count of numbers so
;; copied. The numbers in output are returned in sorted order.

sortedprimes:

;; Within this function:
;; eax = the number currently being tested for primality;
;; ecx = the potential divisor being tested;
;; esi = the pointer to the next number to test for primality;
;; edi = a pointer into the output buffer; and
;; (eax on the stack) = how many numbers are in the output buffer.

;; Initialize the return value to zero, and point esi at the input buffer.

                xor     eax, eax
                pusha
                mov     esi, [byte esp + 36]

;; Retrieve the next number to be tested. If the number is one, it is
;; skipped. If the number is zero, the program has reached the end of
;; the buffer and exits. Otherwise the program starts testing
;; potential divisors, starting with 2.

.nextnumber:    lodsd
                mov     ecx, 2
                cmp     eax, byte 1
                jz      .nextnumber
                jns     .divloop
                popa
                ret     8

;; Divide the number by a candidate divisor. If the quotient is less
;; than the candidate, the list of; potential divisors has been
;; exhausted, and the program jumps forward. If the remainder is
;; zero, however, then the number is composite, and it is discarded
;; and the program jumps back to get the next number. If neither is
;; true, then ecx is incremented and the next candidate is tested.

.divloop:       xor     edx, edx
                div     ecx
                cmp     eax, ecx
                mov     eax, [byte esi - 4]
                jl      .prime
                inc     ecx
                or      edx, edx
                jnz     .divloop
                jmp     short .nextnumber

;; eax contains a prime. The count of primes is incremented, and eax
;; is temporarily placed into the output buffer at the initial position,
;; displacing whatever number was already there. This number is then
;; restored, edi is advanced and eax displaces the number at at the
;; next position. Thus continues until (a) a number higher than eax
;; is reached, in which case it is left there and the displaced
;; number is left in eax, to become the displacing number going
;; forward, or (b) the end of the list is reached, in which case the
;; last number displaced is just zero-padding, and it is discarded as
;; the program jumps back to test the next input number.

.prime:         inc     dword [byte esp + 28]
                mov     edi, [byte esp + 40]
.insertloop:    xchg    eax, [edi]
                or      eax, eax
                jz      .nextnumber
                scasd
                jg      .insertloop
                xchg    eax, [byte edi - 4]
                jmp     short .insertloop

@Sir_Lagsalot is right that all of our solutions are starting to look the same. I was actually a bit dismayed when I finally read Alexander Bakulin's solution at how closely it resembled my own. I guess that's a side effect of targeting the challenge to a single language/platform.

I think lodsd/scasd require direction flag to be cleared.

And it's no wonder that our solutions are converging. I guess this challenge has become rather a collective hacking session than a competition.

@AlexanderBakulin, the standard C calling convention explicitly requires functions to leave the direction flag cleared.

I would appreciate if you point me to the documentation stating it. The only mention of this requirement I could find is in some MASM Guide dated 1992. Neither Wikipedia, nor MSDN don't say a word on it.

It's not just targeting a single language, it's also the stated problem lends itself to one solution with no neat tricks available.

@AlexanderBakulin: Yes, it's been a standard for that long. I think most sources don't bother to mention it anymore because leaving DF set is so obviously catastrophic. As for documentation, see page 3-12 of the ELF ABI standard for 32-bit x86, or section 3.2.1 of the ELF ABI standard for x86-64.  Also, this page seems to have a thorough listing of every calling convention there ever was.

@AlexanderBakulin, see also Agner Fog's documentation on calling conventions. Actually, see Agner Fog's documents in general if you haven't already.

(Sorry for nitpicking.) I tried to disassemble a single Windows API function call. Arguments are pushed in right to left order (so it's __stdcall), but there's no cld or popf or whatever else that could affect the direction flag before call.

Hmmm, but putting __asm { std }; before calling, say, MessageBoxA, results in application crash.

@AlexanderBakulin Argh, I tested it with a cdecl call. My error.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Subtracting, the old-fashioned way
Overview
Adding slightly to the complexity of working with Roman numerals...
The ancient Romans devised a number system using Latin letters, which served them well, and which is still used by modern civilization, though to a much smaller degree. In the time of its use, Romans would have had to learn to use and manipulate these numbers in order to be of much use for many applications. For example, if a man owned 35 oxen, and he sold 27 of them, how would he know the new total other than counting them all? (Ok, that and using an abacus...) If the Romans could do it, surely we can figure it out as well.
Objective
Write the shortest algorithm/function/program that will subtract two Roman numerals together and output the result without converting the string representation of either input into a number.
Rules/Constraints
Because of historical/pre-medieval inconsistencies in formatting, I'm going to outline some non-standard (per modern usage) rules for orthography. See the value guide below as an example.

Since we are subtracting, negative numbers are permissible. 0s, as they have no representation in the Roman system, should be returned as NULL or an empty string.
The letters I, X, C, and M can be repeated up to four times in succession, but no more. D, L, and V can never be repeated.
The letter immediately to the right of another letter in the Roman representation will be of the same or lesser value than that to its left.

In other words, VIIII == 9 but IX != 9 and is invalid/not allowed.

All input values will be 2,000 (MM) or less; no representation for numbers greater than M is necessary.
All input values will be a valid Roman numeral, pursuant to the rules above.
You may not convert any numbers to decimal, binary, or any other number system as part of your solution (you are welcome to use such a method to VERIFY your results).
This is code golf, so shortest code wins.

I do have a solution to this problem that has already been beaten, but I'll hold off on posting it for a few days to see if any other answers come up.
Value Guide
Symbol        Value
I             1
II            2
III           3
IIII          4
V             5
VIIII         9
X             10
XIIII         14
XXXXIIII      44
L             50
LXXXXVIIII    99
C             100
D             500
M             1,000

Examples
XII - VIII = IIII (12 - 8 = 4)
MCCXXII - MCCXXII = '' (2,222 - 2,222 = 0)
XXIIII - XXXXII = -XVIII (24 - 42 = -18)

If any further clarification is needed, please ask.

IX is invalid? Those aren't Roman numerals then, are they?

@leftaroundabout Depending on the era and convention of use, IX is valid in some (most) cases, but I am excluding it from this challenge.

VIIII was sometimes used, sometimes not, but IX is usually always valid in every usage.

Your last example has a + instead of a -

@vsz However, given that VIIII is valid (at least sometimes), and preceding lower-value numerals significantly complicates things, I have chosen to exclude IX (and others) from the challenge. Perhaps that can be saved for another generation of similar challenges?

IV is generally used in place of IIII.

@ObsessiveFOSS Yes, it is, but for this challenge, I am choosing to restrict in this way.

@Gaffi This makes the challenge less interesting. This rule feels like it was added just to enable a specific simple algorithm.

@dystroy It does make it more simple, but this was not meant to turn people off from the challenge. If you prefer to create something that works with a more standard format, then please do!

@dystroy No one is forcing you to do this question... Don't complain about the rules of a question to that you're not contributing... Gaffi has set them, please respect Gaffi's wishes...

@Gaffi What if we're dealing with something like I - -II (1- -2), do we still work this out? Or must both initial Roman numbers be positive?

@WallyWest I don't know that I can actually recall from that far back ;), but looking at it again, I'm thinking the impression was that the supplied values would always be positive.

sed 144
Most of you will know this little episode from roman times, when Cesar invented the Cesar crypting (aka rot13) using SED.
As a big fanatic of SED, he printed the most common used commands: substitute, print, quit and read (SPQR) on signs which he carried with him to teach his soldiers the use of SED.
#  63 = sed-file
#  81 = this
# 144 summa summarum
tac a|rev|sed y/gs/sg/ >b
echo $1|sed -f a|sed "s/$(echo $2|sed -f a)//"|sed -f b

first version 181:
# 126 = 2 sed-files =126
#  55 = this
# 181 summa summarum
echo $1|sed -f a|sed "s/$(echo $2|sed -f a)//"|sed -f b

2 files to use which count to the solution:
a:
s/M/DD/g
s/D/CCCCC/g
s/C/LL/g
s/L/XXXXX/g
s/X/VV/g
s/V/IIIII/g

b:
s/IIIII/V/g
s/VV/X/g
s/XXXXX/L/g
s/LL/C/g
s/CCCCC/D/g
s/DD/M/g

but b can be produced with the first line of the new solution from a: it is - more or less - the inverse, and so we read the file from bottom to top (tac) and from right to left (rev), and switch s and g which are now in the wrong order.
Invocation:
./cg-6061-roman-minus.sh MDCCCCLXV LXVI
MDCCCLXXXXVIIII

I guess I can golf this further, but I liked to occupy wallstreet the sed slot. :)
Since the logic isn't only in the sed files, but in the invocation too, I sum it all up. It could be argued about echo $1, but what about the nested $2? Let's just sum it together.
The sedfiles are pretty long and very redundant in their structure. There seems to be room for optimization.
Luckily, the romans already had QVANTVM <OMPVTVVMZ, so they didn't care for the otherwise lousy performance.
tl;dr:
I convert both numbers into church numerals (IIIIII=6), remove the second from the first, and reconvert the result back.
s.e.d. - sod errat demonstrandum.

@Gaffi: Thanks, but I guess I have to solve the NULL-constraint too. My first idea was that it would only be a few characters, but ... - more than I thought.

Ruby, 112 characters
Using the same idea - but considerably longer than the add-version:
f=->a,b{r=0;v=5;n="IVXLCDM".gsub(/./){|g|r+=a.count(g)-b.count(g);t=r%v;r/=v;v^=7;g*t}.reverse;r<0?"-"+f[b,a]:n}

It is an implementation as a function. Takes two strings and returns the result when subtracting the second from the first. Examples:
puts f["XII", "VIII"]          # -> IIII
puts f["MCCXXII", "MCCXXII"]   # ->
puts f["XXIIII", "XXXXII"]     # -> -XVIII

Your solution uses binary numbers for most calculations. If I read the spec correctly, a sumbission must be entirely free of direct arithmetic since that is nearly always implemented in binary.

Sed, 146 chars
:;s/M/DD/;s/D/CCCCC/;s/C/LL/;s/L/XXXXX/;s/X/VV/;s/V/IIIII/;t;s/\(I\+\)-\1/-/;:a;s/IIIII/V/;s/VV/X/;s/XXXXX/L/;s/LL/C/;s/CCCCC/D/;s/DD/M/;ta;s/-$//

This is a pure sed implementation.
Input is expected to be in the following format, with no spaces
XXIIII-XXXXII

It outputs negative values correctly, and prints zeros as empty strings.
still trying to shave a bit off the code without resorting to using extended regexps

Sed, 154 chars
This is a table driven implementation, correctly outputs negative numbers. expects input in the form of V-VI
s/$/;,MDD,DCCCCC,CLL,LXXXXX,XVV,VIIIII,/;:;s/\([^;]\)\(.*;.*,\1\([^,]\+\),\)/\3\2/;t;s/\(I*\)-\1/-/;:b;s/\([^;]\+\)\(.*;.*,\(.\)\1,\)/\3\2/;tb;s/-*;.*$//;

VBA - 396
Function s(f,c)
a=Split("I,V,X,L,C,D,M",",")
For i=6 To 0 Step -1
x=Replace(f,a(i),""):y=Replace(c,a(i),""):m=Len(f)-Len(x):n=Len(c)-Len(y)
If b=0 Then b=IIf(m>=n,IIf(m=n,0,1),2)
Next
q=f:p=c
If b=1 Then:p=f:q=c
For i=0 To 6
x=Replace(p,a(i),"")
y=Replace(q,a(i),"")
t=(Len(p)-Len(x)-u)-(Len(q)-Len(y))
r=IIf(i Mod 2,2,5)
u=IIf(t<0,1,0)
t=IIf(t<0,t+r,t)
s=String(t,a(i)) & s
Next
If b=2 Then s="-" & s
End Function

Erlang 392
-module(r).
-export([s/2,n/1]).
e(L)->[Y||X<-L,Y<-t([X])].
-define(T(A,B),t(??A)->e(??B);).
?T(M,DD)?T(D,CCCCC)?T(C,LL)?T(L,XXXXX)?T(X,VV)?T(V,IIIII)t(L)->L.
s([H|A],[H|B])->s(A,B);s(R,[])->n(R);s([],R)->[$-|n(R)];s(A,B)->s(e(A),e(B)).
n(L)->d(c(l(x(v(i(L)))))).
-define(E(F,A,B),F(??A++X)->??B++F(X);F(X)->X).
?E(i,IIIII,V).
?E(v,VV,X).
?E(x,XXXXX,L).
?E(l,LL,C).
?E(c,CCCCC,D).
?E(d,DD,M).

Usage:
1> c(r).
{ok,r}
2> r:s("XXIIII","XXXXII").
"-XVIII"
3> r:s("MCCXXII","MCCXXII").
[]
4> r:s("XII","VIII").
"IIII"

JavaScript 276
I honestly thought I could make this smaller... Alas, not as easy as one might think... I'd appreciate any help with reducing this even further...
a="IIIII0VV0XXXXX0LL0CCCCC0DD0M".split(0);d=(e,b)=>e.replace(g=RegExp((c=z)>b?a[c][0]:a[c],"g"),c>b?a[b]:a[b][0]);x=(w=prompt().split("-"))[0];y=w[1];for(z=6;0<z;z--)x=d(x,z-1),y=d(y,z-1);r=x>=y?x.replace(y,""):y.replace(x,"");for(z=0;6>z;z++)r=d(r,z+1);alert((x>=y?"":"-")+r)

C++ 581 478
#define A [j]==a[i]?
#define B for(j=0;j<
#define C .length();j++){
#define E 1:0)
#include <iostream>
int main(){int b=0,m=0,n=0,k,l,j,i,u=0,r,t;std::string x,y,q,p,s,a="IVXLCDM";std::cin>>x>>y;for(i=6;i>=0;i--){B x C m+=(x A E;}B y C n+=(y A E;}b=(b==0?(m>=n?(m!=n?E:2):b);}if(b==1){p=x;q=y;}else{p=y;q=x;}for(i=0;i<7;i++){k=0;l=0;B p C k+=(p A E;}B q C l+=(q A E;}t=(k-u)-l;r=(i%2?2:5);u=(t<0?E;t=(t<0?t+r:t);B t;j++){s=a[i]+s;}}s=(b==2?"-"+s:s);std::cout<<s<<"\n";return 0;}

Python 3, 401
This is a port of my VBA solution, and the length makes me think I need to learn some more about Python. :-/
a="IVXLCDM"
f=input()
c=input()
g=range
s=x=y=z=""
b=u=0
for i in g(6,-1,-1):x,y=f.replace(a[i],z),c.replace(a[i],z);m=len(f)-len(x);n=len(c)-len(y);b=b if(b!=0)else 0 if(m==n)else 1 if(m>n)else 2
q,p=f,c
if(b==1):p,q=f,c
for i in g(7):
 x,y=p.replace(a[i],z),q.replace(a[i],z);t=(len(p)-len(x)-u)-(len(q)-len(y));r=2 if(i%2)else 5;u=1 if(t<0)else 0
 if(t<0):t+=r
 s=a[i]*t+s
if(b==2):s="-"+s
print(s)

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Big integer multiplication
Your challenge (if you choose to accept it) is to implement big integer multiplication in the shortest code possible.
Rules:

Take two integers (decimal form) as ASCII strings from the command line parameters of your program. If your language doesn't support command line parameters, I'll accept stdin or similar input mechanisms.
Output should be in ASCII decimal form, via a standard output mechanism (e.g. stdout)
Must support both positive and negative integers, as well as zero.
Must support any length integer integers up to 2**63 characters long, or at least the maximum you can store in memory.
You may not use any in-built classes or functionality that handles big integers.
The largest data type you may use is a 64-bit unsigned integer.
You may not use floating point operations.
You do not have to implement checks for valid inputs.

Example:
> multiply.exe 1234567890 987654321
1219326311126352690

Enjoy :)

If you say "must support any length integer" you should perhaps add something about performance. Multiplying integers with millions of digits will take really long, at least if we're not supposed to use sophisticated algorithms with FFT and suchlike.

@leftaroundabout: What do you call really long? I guess integers, longer as what is common in many libraries - 64 bit for example - is sufficient. Multiplying 2 numbers of 100 digits each schould be 10000 multiplications and some additions - nothing taking longer than a second in a scripting language.

Boothby is complaining in the comments, that intermediate results of mine will overflow if integers of 'any' length are allowed. Now my algorithm produces a list of intermediate results which exhausts the memory on my machine for a multiplication of about 2000 * 2000 digits. I can increase the RAM for the machine to reach 16.000 digits squared. And switch to a 64bit-System, and increase it further. However, the algorithm would - given no RAM limit - reach 25M digits squared - about 10 books of 500 pages of 60 rows of 60 digits each. With Long 20 billion such books. Isn't that enough?

@userunknown, "any" length was specified.  To me, that's an algorithmic requirement that says if you get a bigger, faster computer 100 years down the road, the implementation won't suddenly start overflowing somewhere.  I mean, why else would that requirement be in there?

any is italicised for emphasis,  I guess. I wonder how many answers will fail if the number of digits exceeds 2**64 :) Why not drop the any and put a sensible limit

I've altered the rules to state that the minimum requirement is 2**63 characters long (i.e. the most you can count in a signed 64-bit integer).

I can't pass a String with a length exceeding Int.MaxValue, since the index of characters in a String is held in an Int. That should be a limit for all JVM-languages. I don't know for C/C++/C# and know nothing about APL.

@userunknown Solutions that work to the absolute limitations of the language are acceptable.

So... to be extremely pedantic (sorry guys, I'm a mathematician, this is what I think about day to day): if you require 2**63 character inputs, well... one of those actually fills up the maximum addressable space of 2**63.  Thus, you can't actually store the inputs in memory!  Ouch.  Set the limit to 2**61 so we can store both the inputs and output in memory.

@boothby See the clarification in the question: "integers up to 2**63 characters long, or at least the maximum you can store in memory."

APL (124 120 116)
This is way too long. It does grade school multiplication.
N←{↓⌽↑⌽¨⍵}⋄S↓'-',A/⍨∨\×A←{∨/M←9<T←0,⍵:∇(1⌽M)+T-M×10⋄⍵}⊃+/N↑⍨⌿2L⍴E,(L-1)+⍳L←⊃⍴E←⌽Y∘×¨⊃X Y←N⍎¨¨A~¨'-'⊣S←1≠+/'-'∊¨A←⍞⍞

Explanation:

N←{↓⌽↑⌽¨⍵}: N is a function that, given a vector of vectors, makes all the vectors the same length, padding with zeroes at the front. It does this by reversing all inner vectors (⌽¨), turning the vector of vectors into a matrix (↑), reversing this matrix (⌽), and turning it back into a vector of vectors (↓).
S←1≠+/'-'∊¨A←⍞⍞: Read two lines of input, as characters (⍞⍞), store them in A, and count how many minuses there are in the input. S is zero or one depending on whether the result will be positive.
X Y←N⍎¨¨A~¨'-': In A (our input) without (~) the minuses, evaluate each separate character (⍎¨¨), run it through the N function and save the two vectors in X and Y. If the input was 123 32, we now have X=1 2 3 Y=0 3 2.
L←⊃⍴E←⌽Y∘×¨⊃X Y: For each digit in the first vector, produce a vector with the digits from the second vector multiplied by that digit. Reverse this vector of vectors so that the least significant one is at the front. Store this vector in E and its length in L.
+/N↑⍨⌿2L⍴E,(L-1)+⍳L: Shift all of these vectors left, padding with zeroes on the right, by their index. Run them through N again so that they're all the same length. Then add all these vectors together. I.e.:

       1 2 3
         3 2
      ------
       2 4 6 (shift 0)
     3 6 9   (shift 1)
    --------
    3 8 13 6 (before carry)
     3 9 3 6 (after carry)

A←{∨/M←9<T←0,⍵:∇(1⌽M)+T-M×10⋄⍵}: Carry the ones. As long as there are still 'digits' higher than 10 (∨/M←9<T←0,⍵), add one to the next significant digit (∇(1⌽M)+T) and remove 10 from the offending digit (-M×10).
'-',A/⍨∨\×A: Remove any leading zeroes from the result vector, and add a minus in front.
S↓: Remove S characters from the front, i.e. if the result is supposed to be positive then remove the minus again.

Wow... An APL program that takes more than 80 characters. I don't know whether I should be impressed or dissatisfied...

Javascript, 147 chars
a=prompt(b=prompt(j=c=[]))
for(i=a.length;j--||(j=b.length,n=0,i--);)c[i+j]=(n=~~c[i+j]+n/10+~~b[j-1]*~~a[i]|0)%10
" -"[10>a[0]^10>b[0]]+c.join("")

How does this output the result? I tried it on jsFiddle (http://jsfiddle.net/SnQ7G/) but apparently it doesn't display anything

@w0lf run in the console of your favorite webbrowser

+1 yes, it works, and I learned something new today :). One thing you could fix though - get rid of the leading zeroes

Isn't this invalid on its face because it uses floating-point math by the rules, given that JavaScript only supports floating-point scalars?

Scala 567 519
type I=List[Long]
type S=String
object C extends App{
def g(l:I,s:I=Nil,i:Long=0L):I=if(l.isEmpty)(i/10::i%10::s).dropWhile(_==0)else
g(l.tail,(l(0)+i)%10::s,(l(0)+i)/10)
def m(p:S,q:S)=g((p.reverse.zipWithIndex.map{a=>q.reverse.zipWithIndex.map(b=>((""+a._1).toLong*(""+ b._1).toLong,a._2+b._2))}.flatten.groupBy(_._2).map(m=>(m._1,m._2.map(_._1)sum))).toList.sortBy(_._1).map(_._2)).mkString
def f(s:S,t:S)=(if((s+t).matches("[^-]*-[^-]*"))"-"else"")+m(s.filter(_!='-'),t.filter(_!='-'))
println(f(args(0),args(1)))
}

updated: Use some Longs for intermediate values, while in fact long Ints passed as Strings can't exceed the length of Int.MaxValue.
Far away from the APL-range, this compilable Scala code multiplies 2 ints of 100digits in about a second on a 7 y'o machine.
I have an ungolfed version which doesn't work :) . Method m seemed to work with a loop, but only because for some map sizes, the map was sorted in the way the g-Method expected the values.
Of course I can sort it, but then I got problems with leading/trailing zeros, or 1-digit values. I tried with ("12345").map in the REPL, and it worked quickly, so I made a test how far I could golf the loop-version, and got nearly the same result - 143 chars here, 145 chars there, so I took my working solution.
So how does the code work: 3 methods:

f) evaluate sign with regex, to append it in the end, and remove the - when calling b)
m) zips both Strings with indexes, mupltiplies each digit with each and sums their indexes. Then groups by index sum, sorts by index sum, sums the values therein. Hands the List of values to c)
g) takes the number, and keeps the last digit. Divides the rest and adds it to the head of the rest of the list, which gets proceeded the same way until empty.

From the REPL, multiplying 1234567890 987654321
The first column from below shows the result digit calculated, except the leading digit which is the overflow from the last computation, and is in column 2.
Replaying:
sum((p.reverse.zipWithIndex.map{a=>q.reverse.zipWithIndex.map(b=>((""+a._1).toInt*(""+ b._1).toInt,a._2+b._2))}.flatten.groupBy(_._2).map(m=>(m._1,m._2.map(_._1)sum))).toList.sortBy(_._1).map(_._2)).mkString.reverse
    0  : 0  ::  List(9, 26, 50, 80, 115, 154, 196, 240, 285, 240, 196, 154, 115, 80, 50, 26, 9)
    9  : 0  ::  List(26, 50, 80, 115, 154, 196, 240, 285, 240, 196, 154, 115, 80, 50, 26, 9)
    6  : 2  ::  List(50, 80, 115, 154, 196, 240, 285, 240, 196, 154, 115, 80, 50, 26, 9)
    2  : 5  ::  List(80, 115, 154, 196, 240, 285, 240, 196, 154, 115, 80, 50, 26, 9)
    5  : 8  ::  List(115, 154, 196, 240, 285, 240, 196, 154, 115, 80, 50, 26, 9)
    3  : 12  ::  List(154, 196, 240, 285, 240, 196, 154, 115, 80, 50, 26, 9)
    6  : 16  ::  List(196, 240, 285, 240, 196, 154, 115, 80, 50, 26, 9)
    2  : 21  ::  List(240, 285, 240, 196, 154, 115, 80, 50, 26, 9)
    1  : 26  ::  List(285, 240, 196, 154, 115, 80, 50, 26, 9)
    1  : 31  ::  List(240, 196, 154, 115, 80, 50, 26, 9)
    1  : 27  ::  List(196, 154, 115, 80, 50, 26, 9)
    3  : 22  ::  List(154, 115, 80, 50, 26, 9)
    6  : 17  ::  List(115, 80, 50, 26, 9)
    2  : 13  ::  List(80, 50, 26, 9)
    3  : 9  ::  List(50, 26, 9)
    9  : 5  ::  List(26, 9)
    1  : 3  ::  List(9)
    2  : 1  ::  List()
    res45: String = 1219326311126352690

...321 * ...890 leads to
index   Product of
sum     Digits
0 =>             1*0 =>      0 => 0
1 =>       2*0 + 1*9 =>    0+9 => 9
2 => 3*0 + 2*9 + 1*8 => 0+18+8 =>26

Ungolfed version:
object BigMul extends App {
   // i is the overrun from the previous value
  def oSum (l: List[Int], sofar: List[Int] = Nil, i: Int=0): List[Int] = {
    /*
    println (sofar + " <- " + (i/10) + "  : " + (({
        if (l.isEmpty) 0 else l.head} +i) %10) + "  ::  " + {
      if (l.isEmpty) "()" else l.tail} )
    */
    if (l.isEmpty) (i / 10 :: i%10 :: sofar).dropWhile (_==0)  else
    oSum (l.tail, (l.head + i) % 10 :: sofar, (l.head + i) / 10)
  }

  // works, but not really ungolfed:
  /* well, yes, this is mapple-di-map
  def mul (p:String,q:String)=
    osum ((p.reverse.zipWithIndex.map {a=>
          q.reverse.zipWithIndex.map (b=>
       (("" + a._1).toInt * ("" + b._1).toInt, a._2 + b._2))}.
       flatten.groupBy (_._2).map (m=>
         (m._1, m._2.map (_._1)sum))).
         toList.sortBy (_._1).map (_._2)).mkString
  */
  // buggy version, but nearly there:
  def mul (s: String, t: String) = {
    val li = for (i <- (s.size -1 to 0 by -1);
      j <- (t.size -1 to 0 by -1);
       a=("" + s(i)).toInt;
      b=("" + t(j)).toInt)
        yield (a*b, i + j)
    osum ((li groupBy (_._2)).toList.sortBy (_._1).
      map (_._2.map (_._1).sum)).
      init.mkString.reverse+"0"
  }

  def signedMul (s: String, t: String) = (s(0), t(0)) match {
    case ('-', '-') => mul (s.tail, t.tail)
    case ('-',   _) => "-"+ mul (s.tail, t)
    case (  _, '-') => "-"+ mul (s, t.tail)
    case (  _,   _) => mul (s, t)
  }

  println (signedMul (args (0), args (1)))
}

looks like those central terms are growing... I'm betting you'll blow the 64-bit limit with long enough inputs.

@boothby: That's right. If I multiply "9'999'999'999" (10 digits) with itself, the maximum intermediate value is 810, for 100 nines it is 8100 and for 1k 9s 8'100. At around 50 million nines, which is about 10 books of 500 pages of 70 rows of 60 digits put into the product we reach 4G, the maxint value. To push the border away, I could change the Int to Long which would cost one character. This would allow for 10G of Books full of digits to multiply. Unfortunately, my machine complains already when using 5000*5000 digits about missing Heap to perform the operation, and this is far, far away...

... from the limits of intermediate results, represented as Int (which is 2^32 for Scala, not 64, btw.).

ok, so this will overflow for '9'*(2**26) squared, which is about 67 gigs.  I regularly use a machine with 128GB of RAM, and machines with 256GB (probably more) are available today.

No. My code produces a list of products, and this list is a(0).size * a(1).size in length, hence it can't produce a result for more than sqrt (Int.MaxValue) digits * 2. However, it finishes a test on 2 inputs, each over 200 digits of nines in less than a second, while your python solution already takes several hours to multiply two shorts. 25 s to multiply 999 by 9999 - that is what a 10 y'o child can reach with pen and paper. I beg I can verify every result you produce, but you can't - not even in 50 years or with your impressing machines. Now completed 9999² in nearly 5 minutes! :)

My solution is not meant for speed, it's meant for correctness.  Assuming a correct Python implementation and a correctly behaving processor, my code will never produce an incorrect answer -- if there's a problem, it's out of memory.  Your code, on the other hand, can produce incorrect output without warning the user.  Anybody can write fast, incorrect code.  Also, I should note that executing code for a few examples is not a proof of correctness.

Well, yes, of course correctness is more important than speed, but if your speed isn't sufficient to multiply two higher shorts, it is completely useless. I could use my own datatype to store the intermediate values, but I could never test it for the interesting values, exceeding MaxInteger, because the memory is exhausted before. But I can test it for values, much bigger than MaxLong.

Only commenting because I'm enjoying how long this has gone on.  :) For what it's worth, I did describe my solution as "utterly utterly terrible".

@Lưu Vĩnh Phúc Your funky edit on emphasis on Ints and Longs isn't consistently applied to Strings, and do you know why? Because it's wrong. It's a typographical nightmare. You wouldn't write 'Clintons either.

C# 619 585
using System.Linq;class P{static void Main(string[] a){var p=new P();string m=p.S(a[0]),n=p.S(a[1]);var l=m.Length+n.Length;var r=p.s+p.C(Enumerable.Range(0,l).Reverse().Select(j=>n.Reverse().Select((y,i)=>(p.C(m.Reverse().Select(z=>(y-48)*(z-48)).ToArray())+new string('0',i)).PadLeft(l,'0')).Select(s=>s[j]-48).Sum()).ToArray()).TrimStart('0');System.Console.WriteLine(r!=""?r:"0");}string C(int[]e){var i=0;var r="";foreach(var z in e.Select(z=>z+i)){i=z/10;r=z%10+r;}return i+r;}string s="";string S(string a){if(!a.StartsWith("-"))return a;s=s==""?"-":"";return a.Substring(1);}}

Test link: http://ideone.com/ghY9G0 (with a small modification: in ideone the input is taken from stdin, as I don't think it's possible to pass command line args).

There is a space that can be removed at if (!a.StartsWith.... Also, I think that string m=p.S(a[0]) can use a var instead.

@TuukkaX You are right. There are also a lot of extra newlines. I will fix this when I have the time. Thanks!

Python, 174 Chars (Positive Only)
import sys
a,b=sys.argv[1:]
l=len(a+b)
x=map(int,a[::-1]+'0'*l+b)
i=r=0
t=""
while i<l:r+=sum(x[i-j]*x[-1-j]for j in range(i+1));t=str(r%10)+t;r/=10;i+=1
print t.lstrip('0')

"Must support both positive and negative integers, as well as zero." - this also does not support zero (prints an empty string)

@w0lf, Truth is, when I wrote "positive only", I meant that I don't support negative numbers. But as you point out, I was 100% accurate. Yes, I know, it means this isn't a valid answer. I put it in the title to make it clear. I may improve it later.

I don't think this is quite kosher... sum(x[i-j]*x[-1-j]for... will likely overflow for i>2**64

In ugoren's solution, i is approximately the length of the result of the multiplication. Due to constraints of the memory architecture on x86 (and ARM and most other architectures) no string can have a longer length than fits in a machine word. Therefore any implementation that handles multiplicands on the order of 2**64 must necessarily write to disk or run in multiple processes, which is a ridiculous requirement for a code golf question. Besides, there is a limit to the length of command line arguments to programs, meaning your own instructions dictate that i << 2**64 in all cases.

I have to agree with Clueless here. When I said any length, I wasn't really saying "you must page to disk if you run out of physical memory". That'd be crazy! :P

My complaint stands, even with the changed rules: 81 > 2^6, so this will overflow on '9'*(2**58) squared.

Note that -1-j can be written as ~j.

GolfScript, 117 chars
-1%" "/~0{1$)\;45={)2%\);\}*}:l~@\l@@""\{15&2$0\{15&2$*+@.!{"\0"+}*(@+@\.10/\10%}%[\](\+@;\;\0\+\}/\;{`+}*\{"-"+}*-1%

Two numbers (optional '-'-sign is supported) separated by space must be given on STDIN. Unfortunately the result printed to STDOUT may have leading zeros.
It is a direct approach implemented in golfscript so it should still be possible to golf this program further.

I think something is wrong - when I run it for 12 x 1 I get 21 (works fine for 1 x 12, though)

Sorry, it was my mistake, I didn't pay attention to the input format. It works fine.

Does this actually work? If so, it's the shortest solution.

Python, 327
This is utterly terrible.  Utterly utterly terrible.  I could probably tighten it up (performance- and golf-wise) by implementing proper addition.  Instead, I use successive addition & subtraction, brainfuck style.  UTTERLY. TERRIBLE.  But I guarantee I never blow the 64-bit limit, unlike some other solutions I'm not going to mention. (only... I already commented on them, and I think I just mentioned them)
import sys
a,b=sys.argv[1:]
s=a[0]<'0'
t=b[0]<'0'
a=a[s:][::-1]
b=b[t:][::-1]
a,b=(map(int,x)for x in(a,b))
def x(c,y,r):
 k=0
 while not-1<c[k]-y<10:c[k]=r;k+=1
 c[k]-=y
 if c[-1]<1:c.pop()
e=[]
a*=1-([0]in(a,b))
while a:
 x(a,1,9);d=b[:]
 while d:x(d,1,9);e+=[0];x(e,-1,0)
print'-'*(s^t)+''.join(map(str,e[::-1]+[0]*(e==[])))

You can store Strings of arbitrary size in Python?

@userunknown, the rules have been updated -- if Python limits string length, that isn't up to me.

Haha! You don't blow the 64-bit limit, but Python does? Wait ...

lol, yup.  This code will work for every possible input for which the input & output fit in memory.  Being base 10, there's a fairly wide gulf between what you can do with your int accumulator and my carries-in-memory -- as I noted on ugoren's solution.

@userunknown: Nope, you can't, but the limit is very high, about 10 **8

I think you can do def x(c,y,r,k=0) and remove the k=0 line to golf one byte.

Haskell, 240 bytes
[d]!n=0#map(*d)n;(d:r)!n=0#(zipWith(+)([d]!n++cycle[0])$0:r!n);0#[]=[];z#[]=[z];z#(x:r)=mod(z+x)10:div(z+x)10#r;r=reverse;l=r.map(read.pure).show.abs;a?b|(a<0)/=(b<0)='-'|0<1=' ';main=do[a,b]<-map read<$>getArgs;putStr$a?b:r(l a!l b>>=show)

Try it online!
Could probably be quite a bit shorter but for the rather inconvenient IO format. Implements the "elementary school" multiplication algorithm, storing and processing numbers as lists of ints, representing each digit of a number.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Write a program that is valid after circular character shift
Potentially very difficult, but I've seen some amazing things come out of this site.
The goal is to write a program, in any language, that does whatever you want. The catch is that the program must be valid after any circular shift of the characters.
A circular character shift is very similar to a Circular Shift. Some examples my clear things up.
For the program int main() { return 0; }
shifting to the left by 6 characters yields: in() { return 0; }int ma
shifting to the left by 1 character yields: nt main() { return 0; }i
shifting to the right by 10 character yields: eturn 0; }int main() { r
However, this program obviously doesn't comply with the rules.
Rules

Any language
Winner is decided by up-vote count
Solutions which do the same thing, or completely different things for each rotation, will receive 100 virtual up-votes to their score.

UPDATE I think this has gone on long enough. The winner, with the most votes (virtual votes included) is Mark Byers. Well done!

There are some very boring potential answers in languages in which an int literal is a valid program. Do they receive a virtual -100?

@PeterTaylor I'm assuming that boring answers will receive less votes.

"Potentially very difficult" It is always helpful to be familiar with a lot of oddball languages before make this kind of statement in a general way. Hard in c or java, sure, but in languages with 1 character commands and simple syntaxes? Not so much.

@dmckee hence the "Potentially"...

@PeterTaylor also in plenty of languages the empty program is a valid program

Use the right language for the task. In this case, that's Befunge.
This language naturally allows rotations because:

All commands are a single character.
The control wraps around when it reaches the end of the program, starting again from the beginning.

This Befunge program prints the exact same output ("Hello") regardless of how many "circular character shifts" you use:
86*01p75*1-02p447**1-03p439**04p439**05p455**1+06p662**07p75*1-08p645**2-09p69*4+019+p57*029+p59*1-039+p555**1-049+p88*059+p86*01p75*1-02p447**1-03p439**04p439**05p455**1+06p662**07p75*1-08p645**2-09p69*4+019+p57*029+p59*1-039+p555**1-049+p88*059+p645**2-00p645**2-00p

It runs on Befungee. It requires that the board is increased (not the 80 character default). It can be run like this:
python befungee.py -w400 hello.bef

It works by first dynamically generating and storing a program that prints "Hello" and then overwriting the first byte to redirect the control into the newly written program. The program is written twice so that if a byte is not written correctly the first time, it will be corrected the second time.
The idea could be extended to produce any program of arbitrary complexity.

Very nice entry!

Brainf*ck
Choose the right tool for the job -- an adage that's never been more relevant than this job right here!
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++.+.>++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++.++++++++++++++.>++++++++++.+

The unshifted program you see here simply prints SHIFT (plus a newline). Abitrarily circular shifts will produce various other outputs, though it will always output six ASCII characters.

Commodore 64 BASIC
? is short for PRINT, and : is a statement separator, so:
?1:?2:?3:          // prints 1, 2, and 3
:?1:?2:?3          // prints 1, 2, and 3
3:?1:?2:?          // adds a program line 3 :PRINT1:PRINT2:PRINT
?3:?1:?2:          // prints 3, 1, and 2
:?3:?1:?2          // prints 3, 1, and 2
2:?3:?1:?          // adds a program line 2 :PRINT3:PRINT1:PRINT
?2:?3:?1:          // prints 2, 3, and 1
:?2:?3:?1          // prints 2, 3, and 1
1:?2:?3:?          // adds a program line 1 :PRINT2:PRINT3:PRINT

Longer variations are, of course, possible:
?1:?2:?3:?4:?5:?6:?7:?8:?9:?10:?11:

etc...

Golfscript
This program prints some digits that always sum up to 2, regardless of how the program is shifted:
10 2 base
0 2 base1
 2 base10
2 base10
 base10 2
base10 2
ase10 2 b
se10 2 ba
e10 2 bas

The first line prints 1010 (10 in binary), the second line prints 02 and all the other lines print 2.
Update:
The program can be tested here. Please note that I've added ns at the end of each row only for formatting the output; these can be removed and the program still works.

Ruby, probably one of the shortest possible solutions:
p

And another slightly longer and more interesting one:
;;p";p;";p

Unary Answer:
000000 ... 00000

^44391 Zeros
Cat program. No matter how you rotate, it's the same program.

x86 16 bit binary
Manually constructed with the help of these (1 2) tables, nasm and ndisasm. This will always return without a crash or infinite loop, because no  bytes are jumps or change the stack and it is filled with NOPs to end with a single byte ret instruction in any case.
In most cases this will output FOO or a substring of that. If AX is broken, this will call a random int 10 (this changed the cursor blinking speed in one of my tests), but it usually does not result in a crash.
To try out, put the hexdump in a file and use xxd -r foo.hex > foo.com, then run in a dos environment (I used dosbox).
Here is a hex dump of this file:
0000000: b846 0d90 90fe c490 9090 bb05 0090 9043  .F.............C
0000010: 43cd 1090 b84f 0d90 90fe c490 9090 bb05  C....O..........
0000020: 0090 9043 43cd 1090 b84f 0d90 90fe c490  ...CC....O......
0000030: 9090 bb05 0090 9043 43cd 1090 9090 c3    .......CC......

And some interesting disassembled offsets:
+0
00000000  B8420D            mov ax,0xd42
00000003  90                nop
00000004  90                nop
00000005  FEC4              inc ah
00000007  90                nop
00000008  90                nop
00000009  90                nop
0000000A  BB0500            mov bx,0x5
0000000D  90                nop
0000000E  90                nop
0000000F  43                inc bx
00000010  43                inc bx
00000011  CD10              int 0x10
00000013  90                nop
00000014  B84F0D            mov ax,0xd4f
00000017  90                nop
00000018  90                nop
00000019  FEC4              inc ah
0000001B  90                nop
0000001C  90                nop
0000001D  90                nop
0000001E  BB0500            mov bx,0x5
00000021  90                nop
00000022  90                nop
00000023  43                inc bx
00000024  43                inc bx
00000025  CD10              int 0x10
00000027  90                nop
00000028  B84F0D            mov ax,0xd4f
0000002B  90                nop
0000002C  90                nop
0000002D  FEC4              inc ah
0000002F  90                nop
00000030  90                nop
00000031  90                nop
00000032  BB0500            mov bx,0x5
00000035  90                nop
00000036  90                nop
00000037  43                inc bx
00000038  43                inc bx
00000039  CD10              int 0x10
0000003B  90                nop
0000003C  90                nop
0000003D  90                nop
0000003E  C3                ret

(for the examples below, the rest of the binary is still valid)
+1
00000000  42                inc dx
00000001  0D9090            or ax,0x9090
00000004  FEC4              inc ah
00000006  90                nop

+2
00000001  0D9090            or ax,0x9090
00000004  FEC4              inc ah
00000006  90                nop

+6
00000000  C4909090          les dx,[bx+si-0x6f70]
00000004  BB0500            mov bx,0x5
00000007  90                nop
00000008  90                nop
00000009  43                inc bx
0000000A  43                inc bx
0000000B  CD10              int 0x10

+11
00000000  050090            add ax,0x9000
00000003  90                nop
00000004  43                inc bx
00000005  43                inc bx
00000006  CD10              int 0x10

+12
00000000  00909043          add [bx+si+0x4390],dl
00000004  43                inc bx
00000005  CD10              int 0x10

+18
00000000  1090B84F          adc [bx+si+0x4fb8],dl
00000004  0D9090            or ax,0x9090
00000007  FEC4              inc ah
00000009  90                nop

(other offsets are just repetitions of the above)
+58
00000000  10909090          adc [bx+si-0x6f70],dl
00000004  C3                ret

PHP
Here you go, a valid PHP program:
Is this still funny?

you should have used a word like "ate" (I'm sure there are longer ones), so that each character shift would still be a real word.

I'm not sure whether to +1 this or -1 this

Scala
A nested quotes:
""""""""""""""""""""""""""""""""

C++/Java/C#/Scala
Comment:
///////////////////////////////////

Empty command:
;;;;;;;;;;;;;;;

Bash
Comment, Whitespace and Shell builtin combination:
#

:

Sed
Standalone valid commands:
p P n N g G d D h H
A combination of the above:
p;P;n;N;g;G;d;D;h;H;
AWK
To print every line of the file:
1

or
//

Don't print anything:
0

Perl
abcd

Looks to me like SED would fail on any odd rotation? Is ;P;n;N;g;G;d;D;h;H valid?

@CMP: yes it is valid.

J
First, a script to check valid rotations of a program s:
check =: 3 :'((<;(". :: (''Err''"_)))@:(y |.~]))"0 i.#y'

For example, the program +/1 5 (sum of 1 and 5) gives:
 check '+/1 5'
┌───────┬───┐
│┌─────┐│6  │
││+/1 5││   │
│└─────┘│   │
├───────┼───┤
│┌─────┐│Err│
││/1 5+││   │
│└─────┘│   │
├───────┼───┤
│┌─────┐│Err│
││1 5+/││   │
│└─────┘│   │
├───────┼───┤
│┌─────┐│6  │
││ 5+/1││   │
│└─────┘│   │
├───────┼───┤
│┌─────┐│6  │
││5+/1 ││   │
│└─────┘│   │
└───────┴───┘

Then, a boring, valid program:
check '1x1'
┌─────┬───────┐
│┌───┐│2.71828│ NB. e^1
││1x1││       │
│└───┘│       │
├─────┼───────┤
│┌───┐│       │ NB. Value of variable x11
││x11││       │
│└───┘│       │
├─────┼───────┤
│┌───┐│11     │ NB. Arbitrary precision integer
││11x││       │
│└───┘│       │
└─────┴───────┘

dc
dc programs are easily valid in any rotation. For example:
4 8 * 2 + p  # 34
8 * 2 + p 4  # stack empty / 10
...

k
.""

Evaluates an empty string
"."

Returns a period character
"".

Returns partial application of '.' (dyanic form) to an empty character list.

Machine Code
How about Z80 / Intel 8051 machine code for NOP.
Sure it does No Operation, but it DOES take up a cycle or two... you can have as many or as few of them as you want.
And I disagree with Ruby answer above - I think a single byte 00h is shorter than a Ruby p.

sh, bash
cc
cc: no input files

cc rotated is cc again, but it is not very friendly if called so naked.
dh
dh: cannot read debian/control: No such file or directory
hd

dh debhelper isn't very cooperative too, while hexdump just waits for input.
gs
sg

Ghostscript starts interactive mode, while switch group shows a usage message - a valid solution here, imho, too.
And here is the script to find candidates for such programs:
#!/bin/bash
for name in /sbin/* /usr/sbin/* /bin/* /usr/bin/*
do
    len=${#name}
    # len=3 => 1:2 0:1, 2:1 0:2
    # len=4 => 1:3 0:1, 2:2 0:2, 3:1 0:3
    for n in $(seq 1 $((len-1)))
    do
        init=${name:n:len-n}
        rest=${name:0:n}
        # echo $init$rest
        which /usr/bin/$init$rest 2>/dev/null >/dev/null && echo $name $init$rest $n
    done
done

If finds longer sequences too, like (arj, jar) or (luatex, texlua) which aren't valid after every shift, but only after some certain shifts, which I misread in the beginning, but there are few, so it is easy to filter them out by hand.

The examples of more than two letters are not valid; the OP said that "the program must be valid after any circular shift". So, arj/jar is not valid, as there is no rja command (although I like this example). +1 for the script - really nice idea :)

Since I was unsure, and not a native English speaker, I consulted a dictionary, where I found it ambiguous, to either mean every, or to mean a random one. The example with shift left by 6, left by 1 and right by 10 assured me in the interpretation, that I just need to find a single shift possibility.

It is not ambiguous. If a program has to be valid after some random shift, then it must also be valid for every possible shift.

@Griffin: Okay - you wrote the question. I removed the longer examples; fortunately there are enough crptc abbrv prgnms in unix like gs and sg. :) Btw.: Are you a native Englisch speaker? In the sentence before, you wrote ... in any language ...  - my solution only works in bash (and sh, zsh, ash and a few else), but all those other solutions take program names too.

Trivial Python example:
"a""b""c""d""e""f""g""h""i""j""k""l""m""n""o""p""q""r""s""t""u""v""w""x""y""z""";print

May be shifted three chars over repeatedly to reveal more and more of the alphabet.

Sorry, I should have made my question clearer. Any shift must produce a valid program. I've updated the question.

Python
123456789.0

Just evaluate some numbers

dc is already used, but the following program always outputs the same, no matter the rotation :D
d

ouputs
dc: stack empty

APL, 1 byte
⍬

Prints empty array. If the program should print something clearly visible:
⍬⍬

Prints a nested array, consisting of two empty arrays:
┌┬┐
│││
└┴┘

In addition, I tried to come up with a program that does something radically different with each shift.
*1⍝ Prints 2.718281828
1⍝* Prints 1
⍝*1 Prints nothing
However, the question arises whether the last line can be considered a program that does something, because it is just a comment that does nothing.


text:
Security by Post-It
As you may know, hackers are everywhere and they want to hack everything. You were asked to make password requirements which will stop any hacker. The problem is, that your boss has heard that paying for LOC is evil and he pays you $1800 - $0.03 * characters inserted per month to make you write simplest thing which possibly could work. So, you have to use small number of characters (hopefully very small), or otherwise forget about cash. Also, your boss doesn't care what language you will use.
The requirements for good passwords are similar to those in mentioned article, except the dictionary based requirements were removed to avoid making solution depend on external files, you don't have to check for letters being rearranged (Hard to understand what it actually means), last rule is removed (What is 3/4?) and it doesn't check old passwords.
The exact requirements after removing certain requirements from linked article are:

have at least 8 character(s)!
not be longer than 12 characters!
have upper and lower case characters!
have no more than 8 upper-case letter(s)!
have no more than 8 lower-case letter(s)!
have at least 2 letter(s)!
have a leading letter!
have at least 1 digit(s)!
not be your username!
not be your username backwards!
not contain your username!
not contain your username backwards!
have no more than 1 pair(s) of repeating characters!
not have 3 occurences of the same character!
not contain carat (^)
not contain space
not contain =
not conatain &
not contain #
not contain ,
not conatain ;
not contain "
not contain >
not contain <
not contain [
not contain |
not contain )

All misspellings on this list were left as is.
$ ./checkpass
Username: John
Password: L!]E2m69
OK.

$ ./checkpass
Username: John
Password: JohnnhoJ12
Nope.

$ ./checkpass
Username: JOE.smith
Password: JOE!smith123
OK.

The shortest code wins money (sent as JPG file). It has to show "Username: " and "Password: " prompts and reply with exact message.

Nice, seeing a code golf challenge in a Daily WTF article, +1 ;-)

The first example should fail ("have upper and lower case characters!"), shouldn't it?

@Howard: It means that both uppercase and lowercase letters are needed in password. Notice lack of word "not".

It's not very obvious in some fonts that the l in that first password is a lower-case ell and not the number one, so I'm editing to replace it with an unambiguous lower-case letter.

@PeterTaylor Ah, thank you. Indeed I read it as 1 (digit one) instead of ell.

Hmm, looks like this one's exceptionally good for regex (I was trying to build a non-regex solution but currently at double the character count for a decently golfed solution).

Perl, 203 194 189 193 chars
Here's my Perl take on the problem:
print"Username: ";chop($u=<>);$n=reverse$u;print"Password: ";$_=<>;
say/^\pL.{7,11}$/*/\d/*/[A-Z]/*9>y/A-Z//&y/a-z//<9*/[a-z]/*
!/[" #,;->^&[|)]|(.)(.*\1.*\1|\1.*(.)\3)|\Q$u\E|\Q$n/?"OK.":"Nope."

The regexes check, in order, that the password:

starts with a letter, has eight to twelve characters
contains a digit
contains an uppercase letter
has eight or fewer uppercase letters
has eight or fewer lowercase letters
contains a lowercase letter
does not contain any of the forbidden punctuation marks, three occurrences of any character, more than one occurrence of a doubled character, the username, or the username reversed.

(Thanks to Peter Taylor for pointing out a bug in the 189-char version.)

Figured out how to run this on ideone with use v5.10; and it fails my "are regexes escaped properly" test case. See http://ideone.com/QKFnZ

@PeterTaylor: I don't know about Ruby, but in Perl fix would be \Q$u\E|\Q$n (the last \E can be skipped, if this part would be moved to end).

OTOH I think one character can be saved by merging the repeats as (.)(.*\1.*\1|\1.*(.)\3) (not tested - I'm not going to try scripting a full test battery with ideone).

Ruby, 270 characters
$><<"Username: ";u=gets.chop
$><<"Password: ";gets
puts ('^.{8,12}$+\p{Lower}+\p{Upper}+^(\p{Alpha}.*){2}+\d+(\p{Lower}.*){9}+(\p{Upper}.*){9}+(.)\1.*(.)\2+(.).*\1.*\1+[ ^=&#,;"<>\[|)]+'+u+?++u.reverse).split(?+).map{|r|/#{r}/=~$_??A:?B}*""=="AAAAABBBBBBB"?"OK.":"Nope."

A ruby implementation build on twelve regular expressions. Each expression is either a positive match (first five) or a negative one (latter seven). As a restriction the username may only contain letters or digits.
Positive regular expression matches:

/^.{8,12}$/: have at least 8 character(s)!, not be longer than 12 characters!
/\p{Lower}/ and /\p{Upper}/: have upper and lower case characters!
/^(\p{Alpha}.*){2}/: have at least 2 letter(s)!, have a leading letter!
/\d/: have at least 1 digit(s)!

Negative regular expression matches:

/(\p{Lower}.*){9}/: have no more than 8 lower-case letter(s)!
/(\p{Upper}.*){9}/: have no more than 8 upper-case letter(s)!
/(.)\1.*(.)\2/: have no more than 1 pair(s) of repeating characters!
/(.).*\1.*\1/: not have 3 occurences of the same character!
/[ ^=&#,;"<>\[|)]/: not contain caret, space, =, &, #, ,, ;, ", >, <, [, |, )
/#{u}/: not be your username!, not contain your username!
/#{u.reverse}/: not be your username backwards!, not contain your username backwards!

This doesn't escape the username, so a perfectly valid password can be rejected. Test case at http://ideone.com/bPpeo

@PeterTaylor That's why I noted the restriction for user names in my answer.

Python 3, 291 bytes/characters
from re import*
n,p=map(input,["Username: ","Password: "])
c,U,L=lambda x:len(split("[%s]"%x,p)),"A-Z","a-z"
print(["OK.","Nope."][any([8>len(p)>12,2>c(U)>9,2>c(L)>9,3>c(U+L),match(U+L,p),2>c("0-9"),n in p,n[::-1]in p,any(c(x)>3 for x in p),len(findall("(.)\\1",p))>1,c(' ^=&#,;"><[|)')>1])])

More nicely formatted and commented:
# import all elements from the regular expression module
from re import *

# Get the two lines of user input (username `n`, password `p`):
n, p = map(input, ["Username: ","Password: "])

# Assign some internally useful shortcuts (uppercase letters `U`, lowercase letters `L`):
# `c(x)` counts the occurrences of pattern `x` in the password `p` plus 1
c, U, L = lambda x: len(split("[%s]" % x, p)), "A-Z", "a-z"

# Print the test result: `"OK."` if the `any(...)` function returned `False`, else `"Nope."`.
# The `any(...)` combines the result of all enclosed checks and returns `True` if at least
# one of the checks failed (returned `True`).
print(["OK.", "Nope."][any([                                # vvv--- CHECKS: ---vvv
                             8>len(p)>12,                   # password length 8-12
                             2>c(U)>9,                      # 1-8 uppercase letters
                             2>c(L)>9,                      # 1-8 lowercase letters
                             3>c(U+L),                      # at least 2 letters
                             match(U+L,p),                  # starts with a letter
                             2>c("0-9"),                    # at least 1 digit
                             n in p,                        # username is not (in) the pw.
                             n[::-1]in p,                   # reversed name not (in) the pw.
                             any(c(x)>3 for x in p),        # at most 3 same characters
                             len(findall("(.)\\1",p))>1,    # at most 1 pair (e.g. "AA")
                             c(' ^=&#,;"><[|)')>1])         # does not contain special char.
                           ])

You can find this solution on ideone.com, but the output looks a bit ugly because it does not show the predefined input or even line breaks there. Also, the username-password combination "JOE.smith"-"JOE!smith123" is currently entered as fixed input data.
I added a breakdown of all the checks as debug output though.


text:
Egyptian Fractions
Overview:
From Wikipedia: An Egyptian fraction is the sum of distinct unit fractions. That is, each fraction in the expression has a numerator equal to 1 and a denominator that is a positive integer, and all the denominators differ from each other. The value of an expression of this type is a positive rational number a/b. Every positive rational number can be represented by an Egyptian fraction.
Challenge:
Write the shortest function that will return the values of all the denominators for the smallest set of unit fractions that add up to a given fraction.
Rules/Constraints:

Input will be two positive integer values.

This can be on STDIN, argv, comma separated, space delimited, or any other method you prefer.

The first input value shall be the numerator and the second input value the denominator.
The first input value shall be less than the second.
The output may include a value(s) that exceeds the memory limitations of your system/language (RAM, MAX_INT, or whatever other code/system constraints exist). If this happens, simply truncate the result at the highest possible value and note that somehow (i.e. ...).
The output should be able to handle a denominator value up to at least 2,147,483,647 (231-1, signed 32-bit int).

A higher value (long, etc.) is perfectly acceptable.

The output shall be a listing of all values of denominators of the smallest set of  unit fractions found (or the fractions themselves, i.e. 1/2).
The output shall be ordered ascending according to the value of the denominator (descending by the value of the fraction).
The output can be delimited any way you wish, but there must be some character between so as to differentiate one value from the next.
This is code golf, so the shortest solution wins.

Exmaples:

Input 1:
43, 48
Output 1:
2, 3, 16
Input 2:
8/11
Output 2:
1/2 1/6 1/22 1/66
Input 3:
5 121
Output 3:
33 121 363

Input/Output 2 should be 8, 11 and 2, 6, 22, 66 right?

Either/Or; they are equivalent. I'd like to leave the formatting up to the creator of the solution.

Is any minimum length fraction OK?  For instance, 8/11 is also 1/2+1/5+1/37+1/4070.

@KeithRandall That would be fine as well. 4 is still 4.

A possible suggestion, to remove abiguity, would be to require the smallest set of unit fractions with the smallest final denominator. For example, 1/2 1/6 1/22 1/66 would be preferable 1/2 1/5 1/37 1/4070 for the input 8/11.

I suggest adding 5/121 = 1/33+1/121+1/363 to the test cases. All greedy programs (including mine) give 5 fractions for it. Example taken from Wikipedia.

@ugoren Added...

@primo I think that if there are multiple minimums, then whichever can be found would be acceptable. If one algorithm can be written with fewer characters as a result, I would not want to hinder that solution.

@Gaffi Can I ask for some clarity on the requirement that the program handles cases that "exceeds the memory limitations of your system"? Does this mean that the program is not at all allowed to fail due to memory exhaustion? My (current) entry uses a fixed amount of memory, but it does fail if an internal value exceeds MAX_INT. Is it acceptable to treat that as the same thing? (And if so, is there a minimum upper limit that the program must accept? Presumably there is; otherwise return x==y?"1":"..." would be a winning entry.)

@breadbox You should account for both memory limitations and MAX_INT (or whatever other code/system constraints exist). Also, you make a good point about exiting prematurely... Fixing question.

@userunknown Yup, it does. Fixed.

Gave +1 since I've actually learned about Egyptian fractions in a History of Math course (and had to do math with with them, as well as finding the fractional sums like this problem.) A nice and creative challenge.

@primo If reducing ambiguity were important for answers, it'd make more sense to me to make the sum of the denominators as low as possible.

Fun fact: the Egyptians also had an independent representation of 2/3 as a single "fraction".

Common Lisp, 137 chars
(defun z(n)(labels((i(n s r)(cond((= n 0)r)((< n(/ 1 s))(i n(ceiling(/ 1 n))r))(t(i(- n(/ 1 s))(1+ s)(cons s r))))))(reverse(i n 2'()))))

(z 43/48) -> (2 3 16)
(z 8/11) -> (2 5 37 4070)
(z 5/121) -> (25 757 763309 873960180913 1527612795642093418846225)
No need to worry about huge numbers, or handling fractional notation!

(defun z(n)(labels((i(n s r)(cond((= n 0)r)((< n(/ 1 s))(i n(ceiling(/ 1 n))r))(t(i(- n(/ 1 s))(1+ s)(cons s r))))))(reverse(i n 2'()))))
(z 43/48)
Show not result in tio... What I have to use for print the result?

(print (z 103/333) )
return one list of 5 numbers but would exist one list of 4 numbers as: 1/4,1/18,1/333,1/1332. So the above function would not return the minimum.

Python 2, 169 167 chars
x,y=input()
def R(n,a,b):
 if n<2:return[b/a][b%a:]
 for m in range((b+a-1)/a,b*n/a):
  L=R(n-1,a*m-b,m*b)
  if L:return[m]+L
n=L=0
while not L:n+=1;L=R(n,x,y)
print L

Takes comma-separated args on stdin and prints a python list on stdout.
$ echo 8,11 | ./egypt.py
[2, 5, 37, 4070]

I think you can save two chars by using tab on the second indentation level. 2. The script doesn't indicate truncation due to exceeding system memory limitations.

In Tio Your code goes out of memory for just 103/45533

Instead in Ideone your code goes in run time error for the same input 103,45533: Runtime error #stdin #stdout #stderr 0.89s 99264KB

PHP 82 bytes
<?for(fscanf(STDIN,"%d%d",$a,$b);$a;)++$i<$b/$a||printf("$i ",$a=$a*$i-$b,$b*=$i);

This could be made shorter, but the current numerator and denominator need to be keep as whole numbers to avoid floating point rounding error (instead of keeping the current fraction).
Sample usage:
$ echo 43 48 | php egyptian-fraction.php
2 3 16
$ echo 8 11 | php egyptian-fraction.php
2 5 37 4070

Comma operator emulated as useless arguments to printf? I should save this trick somewhere.

I'm pretty sure this is a Greedy Algorithm, so it won't always give the smallest set of fractions. If you run it with input like 5 121 or 31 311, it will give the wrong answer (after a very long time).

@grc 31/311 -> {a[1]->11,a[2]->115,a[3]->13570,a[4]->46422970}

C, 163 177 chars
6/6: At last, the program now correctly handles truncation in all cases. It took a lot more chars than I was hoping for, but it was worth it. The program should 100% adhere to the problem requirements now.
d[99],c,z;
r(p,q,n,i){for(c=n+q%p<2,i=q/p;c?d[c++]=i,0:++i<n*q/p;)q>~0U/2/i?c=2:r(i*p-q,i*q,n-1);}
main(a,b){for(scanf("%d%d",&a,&b);!c;r(a,b,++z));while(--c)printf("%d\n",d[c]);}

The program takes the numerator and denominator on standard input. The denominators are printed to standard output, one per line. Truncated output is indicated by printing a zero denominator at the end of the list:
$ ./a.out
2020 2064
2
3
7
402
242004

$ ./a.out
6745 7604
2
3
19
937
1007747
0

The denominators in the second example sum to 95485142815 / 107645519046, which differs from 6745 / 7604 by roughly 1e-14.

Again, I think this is a greedy algorithm.

The outermost loop explores all possible answers of N denominators before it begins testing answers of N+1 denominators. You can call it greedy, I suppose, but I believe it fulfills the stated problem.

Sorry, I take that back. It doesn't follow the greedy solution, but I have found that it isn't completely accurate for some input (31 311 for example).

31 311 overflows, but the program fails to flag it.

Python, 61 chars
Input from STDIN, comma separated.
Output to STDOUT, newline separated.
Doesn't always return the shortest representation (e.g. for 5/121).
a,b=input()
while a:
    i=(b+a-1)/a
    print"1/%d"%i
    a,b=a*i-b,i*b

Characters counted without unneeded newlines (i.e. joining all lines within the while using ;).
The fraction is a/b.
i is b/a rounded up, so I know 1/i <= a/b.
After printing 1/i, I replace a/b with a/b - 1/i, which is (a*i-b)/(i*b).

I want to vote this up, since it is so small, but it's just missing that one piece!

I want to fix this one piece, but then it won't be so small... I have a feeling I'll just reinvent Keith Randall's solution.

C, 94 bytes
n,d,i;main(){scanf("%i%i",&n,&d);for(i=1;n>0&++i>0;){if(n*i>=d)printf("%i ",i),n=n*i-d,d*=i;}}

Try It Online
edit: A shorter version of the code was posted in the comments so I replaced it. Thanks!

Hello, and welcome to the site! This is a [tag:code-golf] competition, so the objective is to make your code as short as possible. It looks like there are lots of things you could do to make your code shorter. For example, you could removed all the unnecessary whitespace from your answer.

@DJMcMayhem Thank you sir, understood and done.

Hi, welcome to PPCG! Could you perhaps add a TryItOnline-link with test code for the test cases in the challenge? Also, some things you could golf: for(i=2;n>0&&i>0;i++) can be for(i=1;n>0&++i>0;); the brackets of the for-loop can be removed (because it only has the if inside); d=d*i; can be d*=i;; and I'm not entirely sure, but I think #include <stdio.h> can be without spaces: #include<stdio.h>. Oh, and it might be interesting to read Tips for golfing in C and Tips for golfing in

@KevinCruijssen Thanks for the tips.

94 bytes.

In Ideone C web compiler server, the input 103/333 return as solution 4 17 2059 9324800 343340800 one length 5 solution, but it would be one array of length 4 that would be good too: 1/4,1/18,1/333,1/1332; so that not return the minimum

Stax, 18 bytes
é├WüsOΩ↨÷╬6H╒σw[▐â

Run and debug it
At each step, it tries to minimize the subsequent numerator.  It seems to work, but I can't prove it.

APL (Dyalog Extended), 7 bytes
⌂efract

Try it online!
From some reason, Dyalog APL has a builtin for this.
Takes the numerator and denominator on the left and the right

Husk, 8 bytes
ḟo=⁰ΣṖİ\

Try it online!
Larger denominators take very long, as we are calculating the powerset of an infinite list.
Takes input as a fraction a/b.
Explanation
ḟo=⁰ΣṖİ\
      İ\ Infinite list [1,1/2,1/3...]
     Ṗ   Powerset
ḟo       first sublist which satisfies:
    Σ    sum
  =⁰     equals input?

AXIOM, 753 bytes
L==>List FRAC INT
macro  M(q)==if c<m or(c=m and m<999 and reduce(max,map(denom,q))<xv)then(m:=c;a:=q;xv:=reduce(max,map(denom,a)))
f(x,n)==(y:=x;a:L:=[];c:=0;q:=denom x;q:=q^4;for i in n.. repeat((c:=c+1)>50=>(a:=[];break);1/i>y=>1;member?(1/i,a)=>1;a:=concat(a,1/i);(y:=y-1/i)=0=>break;numer(y)=1 and ~member?(y,a)=>(a:=concat(a,y);break);(i:=floor(1/y))>q=>(a:=[];break));a)
h(x:FRAC INT):L==(a:L:=[];x>1=>a;numer(x)=1=>[x];n:=max(2,floor(1/x));xv:=m:=999;d:=denom x;zd:=divisors d;z:=copy zd;for i in 2..30 repeat z:=concat(z,i*zd);d:=min(10*d,n+9*m);for i in n..d repeat((c:=maxIndex(b:=f(x,i)))=0=>1;c>m+1=>1;M(b);v:=reduce(+,delete(b,1));for j in z repeat((c:=1+maxIndex(q:=f(v,j)))=1=>1;member?(b.1,q)=>1;q:=concat(b.1,q);M(q)));reverse(sort a))

The idea would be apply the "Greedy Algorithm" with different initial points,
and save the list that has minimum length. But not always it would find the min solution with
less difined: "array A will be less than array B if and only if A has few elements of B,
or if the number of elements of A is the same of number of elements of B, than A it is less than B
if the more little element of A is bigger as number, than the more little element of B".
Ungolfed and test
-- this would be the "Greedy Algorithm"
fracR(x,n)==
   y:=x;a:L:=[];c:=0;q:=denom x;q:=q^4
   for i in n.. repeat
      (c:=c+1)>50   =>(a:=[];break)
      1/i>y         =>1
      member?(1/i,a)=>1
      a:=concat(a,1/i)
      (y:=y-1/i)=0  =>break
      numer(y)=1 and ~member?(y,a)=>(a:=concat(a,y);break)
      (i:=floor(1/y))>q           =>(a:=[];break)
   a

-- Return one List a=[1/x1,...,1/xn] with xn PI and x=r/s=reduce(+,a) or return [] for fail
Frazione2SommaReciproci(x:FRAC INT):L==
    a:L:=[]
    x>1       =>a
    numer(x)=1=>[x]
    n:=max(2,floor(1/x));xv:=m:=999;d:=denom x;zd:=divisors d;z:=copy zd
    for i in 2..30 repeat z:=concat(z,i*zd)
    d:=min(10*d,n+9*m)
    for i in n..d repeat
        (c:=maxIndex(b:=fracR(x,i)))=0=>1
        c>m+1                         =>1
        M(b)
        v:=reduce(+,delete(b,1))
        for j in z repeat
              (c:=1+maxIndex(q:=fracR(v,j)))=1=>1
              member?(b.1,q)                  =>1
              q:=concat(b.1,q)
              M(q)
    reverse(sort a)

(7) -> [[i,h(i)] for i in [1/23,2/23,43/48,8/11,5/121,2020/2064,6745/7604,77/79,732/733]]
   (7)
      1   1      2   1  1      43  1 1  1      8  1 1  1  1
   [[--,[--]], [--,[--,---]], [--,[-,-,--]], [--,[-,-,--,--]],
     23  23     23  12 276     48  2 3 16     11  2 6 22 66
      5    1  1   1      505  1 1 1  1    1
    [---,[--,---,---]], [---,[-,-,-,---,----]],
     121  33 121 363     516  2 3 7 602 1204
     6745  1 1  1  1    1      1       77  1 1 1  1  1   1
    [----,[-,-,--,---,-----,------]], [--,[-,-,-,--,---,---]],
     7604  2 3 19 950 72238 570300     79  2 3 8 79 474 632
     732  1 1 1  1   1    1     1
    [---,[-,-,-,--,----,-----,-----]]]
     733  2 3 7 45 7330 20524 26388
                                                      Type: List List Any
       Time: 0.07 (IN) + 200.50 (EV) + 0.03 (OT) + 9.28 (GC) = 209.88 sec
(8) -> h(124547787/123456789456123456)
   (8)
        1             1                         1
   [---------, ---------------, ---------------------------------,
    991247326  140441667310032  613970685539400439432280360548704
                                     1
    -------------------------------------------------------------------]
    3855153765004125533560441957890277453240310786542602992016409976384
                                              Type: List Fraction Integer
                     Time: 17.73 (EV) + 0.02 (OT) + 1.08 (GC) = 18.83 sec
(9) -> h(27538/27539)
         1 1 1  1  1    1      1        1
   (9)  [-,-,-,--,---,-----,------,----------]
         2 3 7 52 225 10332 826170 1100871525
                                              Type: List Fraction Integer
                     Time: 0.02 (IN) + 28.08 (EV) + 1.28 (GC) = 29.38 sec

reference and numbers from: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fractions/egyptian.html
for add something, this below would be  the one optimized for find min length  fraction that has the max denominator less (and not optimized for lengh)
L==>List FRAC INT

-- this would be the "Greedy Algorithm"
fracR(x,n)==
   y:=x;a:L:=[];c:=0;q:=denom x;q:=q^20
   for i in n.. repeat
      (c:=c+1)>1000  =>(a:=[];break)
      1/i>y          =>1
      member?(1/i,a) =>1
      a:=concat(a,1/i)
      (y:=y-1/i)=0  =>break
      numer(y)=1 and ~member?(y,a)=>(a:=concat(a,y);break)
      (i:=floor(1/y))>q           =>(a:=[];break)
   a

-- Return one List a=[1/x1,...,1/xn] with xn PI and x=r/s=reduce(+,a) or return [] for fail
Frazione2SommaReciproci(x:FRAC INT):L==
    a:L:=[]
    x>1       =>a
    numer(x)=1=>[x]
    n:=max(2,floor(1/x));xv:=m:=999;d:=denom x;zd:=divisors d;z:=copy zd;
    w1:= if d>1.e10 then 1000 else 300; w2:= if d>1.e10 then 1000 else if d>1.e7 then 600 else if d>1.e5 then 500 else if d>1.e3 then 400 else 100;
    for i in 2..w1 repeat(mt:=(i*zd)::List PI;mv:=[yy for yy in mt|yy>=n];z:=sort(removeDuplicates(concat(z,mv)));#z>w2=>break)
    for i in z repeat
        (c:=maxIndex(b:=fracR(x,i)))=0=>1
        c>m+1                         =>1
        if c<m or(c=m and m<999 and reduce(max,map(denom,b))<xv)then(m:=c;a:=b;xv:=reduce(max,map(denom,a)))
        v:=reduce(+,delete(b,1))
        for j in z repeat
              (c:=1+maxIndex(q:=fracR(v,j)))=1=>1
              member?(b.1,q)                  =>1
              q:=concat(b.1,q)
              if c<m or(c=m and m<999 and reduce(max,map(denom,q))<xv)then(m:=c;a:=q;xv:=reduce(max,map(denom,a)))
    reverse(sort a)

the results:
(5) -> [[i,Frazione2SommaReciproci(i)] for i in [1/23,2/23,43/48,8/11,5/121,2020/2064,6745/7604,77/79,732/733]]
   (5)
      1   1      2   1  1      43  1 1  1      8  1 1  1  1
   [[--,[--]], [--,[--,---]], [--,[-,-,--]], [--,[-,-,--,--]],
     23  23     23  12 276     48  2 3 16     11  2 6 22 66
      5    1  1   1      505  1 1 1  1    1
    [---,[--,---,---]], [---,[-,-,-,---,----]],
     121  33 121 363     516  2 3 7 602 1204
     6745  1 1  1  1    1      1       77  1 1 1  1  1   1
    [----,[-,-,--,---,-----,------]], [--,[-,-,-,--,---,---]],
     7604  2 3 19 950 72238 570300     79  2 3 8 79 474 632
     732  1 1 1  1   1    1     1
    [---,[-,-,-,--,----,-----,-----]]]
     733  2 3 7 45 7330 20524 26388
                                                      Type: List List Any
                     Time: 0.08 (IN) + 53.45 (EV) + 3.03 (GC) = 56.57 sec
(6) -> Frazione2SommaReciproci(124547787/123456789456123456)
   (6)
        1            1               1                  1
   [---------, ------------, ----------------, -------------------,
    994074172  347757767307  2764751529594496  1142210063701888512
                      1
    -------------------------------------]
    2531144929865351036156388364636113408
                                              Type: List Fraction Integer
         Time: 0.15 (IN) + 78.30 (EV) + 0.02 (OT) + 5.28 (GC) = 83.75 sec
(7) -> Frazione2SommaReciproci(27538/27539)
         1 1 1  1   1     1       1       1
   (7)  [-,-,-,--,----,-------,-------,-------]
         2 3 7 43 1935 3717765 5204871 7105062
                                              Type: List Fraction Integer
                     Time: 0.05 (IN) + 45.43 (EV) + 2.42 (GC) = 47.90 sec

It seems many good denominators have as factor divisors of the input fraction denominator.

APL(NARS), 2502 bytes
fdn←{1∧÷⍵}⋄fnm←{1∧⍵}⋄ffl←{m←⎕ct⋄⎕ct←0⋄r←⌊⍵⋄⎕ct←m⋄r}⋄divisori←{a[⍋a←{∪×/¨{0=≢⍵:⊂⍬⋄s,(⊂1⌷⍵),¨s←∇1↓⍵}π⍵}⍵]}

r←frRF w;x;y;c;q;i;j
(x i)←w⋄i-←1⋄y←x⋄r←⍬⋄c←0⋄q←fdn x⋄q←q*20
i+←1
→4×⍳∼1000<c+←1⋄→6
j←÷i⋄→2×⍳j>y⋄→2×⍳(⊂j)∊r⋄r←r,(⊂j)⋄y←y-j⋄→0×⍳y=0⋄→5×⍳1≠fnm y⋄→5×⍳(⊂y)∊r⋄r←r,⊂y⋄→0
→2×⍳∼q<i←ffl ÷y
r←⍬

r←fr2SumF x;n;xv;m;d;zd;z;i;b;c;t;v;j;k;q;w1;w2;t;b1
z←r←⍬⋄→0×⍳1≤ffl x
:if 1=fnm x⋄r←,⊂x⋄→0⋄:endif
n←2⌈ffl÷x⋄xv←m←999⋄d←fdn x⋄zd←divisori d
w1←1000⋄w2←50⋄:if d>1.e10⋄w2←700⋄:elseif d>1.e7⋄w2←600⋄:elseif d>1.e5⋄w2←500⋄:elseif d>1.e3⋄w2←400⋄:elseif d>1.e2⋄w2←100⋄:endif
:for i :in ⍳w1⋄z←∪z∪k/⍨{⍵≥n}¨k←i×zd⋄:if w2<≢z⋄:leave⋄:endif⋄:endfor
z←∪z∪zd⋄z←z[⍋z]
:for i :in z
    :if 0=c←≢b←frRF x i ⋄:continue⋄:endif
    :if      c>m+1      ⋄:continue⋄:endif
    :if      c<m        ⋄m←c⋄r←b⋄xv←⌈/fdn¨b
    :elseif (c=m)∧(m<999)
         :if xv>t←⌈/fdn¨b⋄m←c⋄r←b⋄xv←t⋄:endif
    :endif
    :if c≤2⋄:continue⋄:endif
    v←↑+/1↓b⋄b1←(⊂↑b)
    :for j :in z
       :if 1=c←1+≢q←frRF v j⋄:continue⋄:endif
       :if        b1∊q      ⋄:continue⋄:endif
       q←b1,q
       :if  c<m⋄m←c⋄r←q     ⋄xv←⌈/fdn¨q
       :elseif (c=m)∧(m<999)
           :if xv>t←⌈/fdn¨q⋄m←c⋄r←q⋄xv←t⋄:endif
       :endif
    :endfor
:endfor
→0×⍳1≥≢r⋄r←r[⍋fdn¨r]

Traslation from AXIOM code for this problem, to APL, using for the first time
(for me) the fraction type (that is bignum...).
103r233 means the fraction 103/233. Test:
  ⎕fmt fr2SumF 1r23
┌1────┐
│ 1r23│
└~────┘
  ⎕fmt fr2SumF 2r23
┌2──────────┐
│ 1r12 1r276│
└~──────────┘
  ⎕fmt fr2SumF 43r48
┌3────────────┐
│ 1r2 1r3 1r16│
└~────────────┘
  fr2SumF 8r11
1r2 1r6 1r22 1r66
  fr2SumF 5r121
1r33 1r121 1r363
  fr2SumF 2020r2064
1r2 1r3 1r7 1r602 1r1204
  fr2SumF 6745r7604
1r2 1r3 1r19 1r950 1r72238 1r570300
  fr2SumF 77r79
1r2 1r3 1r8 1r79 1r474 1r632
  fr2SumF 732r733
1r2 1r3 1r7 1r45 1r7330 1r20524 1r26388
  fr2SumF 27538r27539
1r2 1r3 1r7 1r43 1r1935 1r3717765 1r5204871 1r7105062
  fr2SumF 124547787r123456789456123456
1r994074172 1r347757767307 1r2764751529594496 1r1142210063701888512
  1r2531144929865351036156388364636113408

GAP, 340 bytes
f:=function(b,l)local x,R;if l=1 then if IsInt(b)then
return[[b]];fi;return[];fi;R:=[];for x in[Int(b)+1..Int(l*b)]do
UniteSet(R,List(Filtered(f(b*x/(x-b),l-1),d->not x in d),s->UnionSet([x],s)));od;return
R;end;e:=function(n,d)local l,R;l:=0;repeat l:=l+1;R:=f(d/n,l);until R<>[];return
Filtered(R,s->s[l]=Minimum(List(R,s->s[l])))[1];end;

Try it online!
The entry function is e, which takes two parameters, the numerator and denominator in that order, as required. 2 characters could be golfed (replace n,d with q and d/n with 1/q) if I may make e take the fraction n/d direct, and 2 more if I may make e take its reciprocal d/n. But this goes against the question.
The helper function f returns a list of the ways to represent 1/b in l distinct terms.


text:
Arithmetic Sequences
An arithmetic sequence is a sequence of numbers of the form a,a+n,a+2n,a+3n, etc. In this case, a and n will both be either integers or decimals.
Given two inputs, a, n, and a top number value, return a list of numbers where the last term is less than or equal to the top number value.
The input can be formatted in any way, as well as the output.
The catch to this problem is dealing with floating point arithmetic errors.
For example, 0.1 + 0.3 * 3 is 1, however this will display 0.99999999999... if you simply go 0.1 + 0.3 * 3. We want 1, not 0.99999999999...
Test Cases
a=2, n=3, top=10: [2, 5, 8]
a=3, n=1.5, top=12: [3, 4.5, 6, 7.5, 9, 10.5, 12]
a=3.14159, n=2.71828, top=10: [3.14159, 5.85987, 8.57815]
a=0.1, n=0.3, top=2: [0.1, 0.4, 0.7, 1, 1.3, 1.6, 1.9]
Shortest code wins. Good luck!

Is this supposed to be a standalone program, or a function? If a standalone program is provided, are there any requirements to the format of the input or output?

Function/standalone is fine. There is no specified input or output: the programmer will state both.

What do you mean by "floating points" in the first paragraph? If they're actual IEEE754 floating point numbers then most of your test cases don't make sense; so are they strings representing decimal floating point numbers? If so, to what precision?

I changed "floating points" to "decimals".

The input/output part should be specified in the question, not just in the comments.

APL (22)
{⍵≤T:⍵,∇⍵+N⋄⍬}⊃A N T←⎕

Reads input from stdin as three whitespace-separated numbers.
This is actually shorter than using the index generator.

This problem was actually a fail. Using the print command, or the equivalent of it, rounded off floating points, so the challenge was not a challenge at all.

Non-golfed haskell, 32
f a n t=takeWhile(<=t)[a,a+n..]

I'd love to change takeWhile to take, but integer division can't be done with /, it needs to be done with div. If I go with / then I need to do implicit conversion which makes it that much longer.

That only works without the floating-point problems if called as f :: Rational -> Rational -> Rational -> Rational rather than e.g. Double -> Double -> Double -> Double. But I doubt output in the form [1 % 10,2 % 5,7 % 10,1 % 1,13 % 10,8 % 5,19 % 10] will be accepted.

@leftaroundabout If it was my problem, I'd accept that output! (But it's not.)

J, 34 33 31 characters
({.+i.@>:@([:<.1{[%~{:-{.)*1{[)

I'm sure there's room for improvement here.
Usage:
   ({.+i.@>:@([:<.1{[%~{:-{.)*1{[)2 3 10
2 5 8

We can give the verb a name for an extra three characters:
   s=.({.+i.@>:@([:<.1{[%~{:-{.)*1{[)
   s 2 3 10
2 5 8

Previously:
((0-.~]*]<:2{[)(((i.100)*1{[)+{.))

Thought I'd have a go at doing this in Golfscript and got as far as .3$- 2$/1+,{2$*}%{3$+}% before realising Golfscript doesn't seem to do floats. Bugger.

bash 12:
seq $1 $2 $3

Haha - who would have thought that? Silly'o'bash which normally just handles Integer arithmetic (9/10 = 0) can handle floating points that way:
./cg-6228-arithmetic-sequences.sh 2 3 10
2
5
8
./cg-6228-arithmetic-sequences.sh 3 1.5 12
3,0
4,5
6,0
7,5
9,0
10,5
12,0

Other test-cases omitted for brevity. I have to mention that you can change the locale, if you're irritated by 10,5 which is the continental way to say 10.5. ;)

How very interesting!

This could be 3 bytes as a function: seq (maybe)

Ruby 34
s=->a,n,t{p a;s[a+n,n,t]if a+n<=t}

Input: the three function parameters
Output: the sequence numbers are printed, one per line
Ideone link: http://ideone.com/SahPs

J, 26
s=:1 :']+u*[:i.@<.@>:u%~-'

There's some interesting syntax to use this definition.

   10(2 s)1
1 3 5 7 9

Ruby - 28
((t-a)/n).times{|i|p(a+i*n)}

Mathematica, 5 bytes
Range

Arguments are a,top,n in that order. I'm assuming that decimal points at the end are okay.

Scala 52
val x,?,z=BigDecimal(readLine)
x to z by?map println

Give inputs a,n and top in the separate line.
Each entry of the output will be listed in the separate line.

Mathematica 39 37
Table[#+#2 k,{k,0,Quotient[#3-#,#2]}]&

Usage
Table[#1 + #2 k, {k, 0, Quotient[#3 - #1, #2]}] &[2, 3, 10]
Table[#1 + #2 k, {k, 0, Quotient[#3 - #1, #2]}] &[3, 1.5, 12]
Table[#1 + #2 k, {k, 0, Quotient[#3 - #1, #2]}] &[3.14159, 2.71828, 10]
Table[#1 + #2 k, {k, 0, Quotient[#3 - #1, #2]}] &[0.1, 0.3, 2]

Swift, 90
Not quite as short as the other ones here but this doesn't use a builtin to compute the sequence, nor does it operate on a standard float type.  It declares a function f(a:n:t:) that takes the numbers in and prints the sequence to stdout.
import Foundation
func f(a:Decimal,n:Decimal,t:Decimal){var x=a
while x<=t{print(x)
x+=n}}

Try it Online! (with hardcoded test case)
I learned a few things while doing this that surprised me:

Swift's range builtin is only iterable for integers, unlike in Python where you can specify the step size.
Assignment operators in Swift return Void, so I couldn't abbreviate the body of the while loop to print(x+=n). I tried it; it just printed () a bunch of times.
Decimal values are not converted to Double when printing. If you replace Decimal in the declaration with Double, it prints 1.0 and 1.9000000000000001 rather than 1 and 1.9. On the other hand, this proves that it is avoiding floating-point rounding errors, as the question specified.
There is no version of the <= operator that lets you compare a Decimal to any other number type, so I can't make the function declaration shorter by changing t's type.

In fact, even though Decimal is ExpressibleByFloatLiteral, it is not FloatingPoint.

You could shave off two bytes by allowing the input to be mutated (changing the function signature to f(a:inout Decimal,n:Decimal,t:Decimal), as this eliminates the need for the variable x.

JavaScript 70
s=prompt().split(",");for(n=0;(p=s[0]-0+n*s[1]-0)<=s[2]-0;n++)alert(p)

input in the form a,n,top

The code gives floating-point arithmetic errors. I, however, used a different test case: I will add it to the list.

Perl, 37 chars
for(($_,$n,$t)=<>;$_<=$t;$_+=$n){say}

Input a, n, and top, each number on a separate line. The list is output with newlines separating the values. Run with perl -M5.010 (or perl -E).

Python (245)
Input should be given with a space in between, e.x. 0.1 0.3 0.5
a=raw_input().split()
I,F=int,float
D='.'
b=[[I(i.replace(D,'')),len(i.split(D)[1:])]for i in a[:2]]
a=map(F,a)
c=max(b,key=lambda x:x[1])[1]
for i in b:i[0]*=10**(c-i[1])
print [(b[0][0]+i*b[1][0])/10.0**c for i in range(I((a[2]-a[0])/a[1]+1))]

It avoids floating point errors by turning each floating point into a list containing two values: the number without the decimal point, and the number of significant digits.
example: 1.34 -> [134, 2]

Python, 37
a,n,t=input()
while a<=t:print a;a+=n

Grabs input in the form a, n, top, and prints out the numbers on separate lines.

C# 120 74
void A(float a,float n,int t){Console.Write(a+" ");a+=n;if(a<=t)A(a,n,t);}

Edit: New version - recursive and a lot shorter than using LINQ :)
Input: the three parameters of method A
Output: the numbers in the sequence are printed to console, separated by spaces.
Test link: http://ideone.com/o7g6k

Previous version (using LINQ):

IEnumerable<float>A(float a,float n,int t){return Enumerable.Range(0,int.MaxValue).Select(i=>a+n*i).TakeWhile(s=>s<=t);}

PHP 83
<?function a($x,$i,$t){while($r<$t){$r=$x+$i*$g++;$s.=($r<$t?$r." ":"");}echo$s;}?>

Wish I could remove "function" but there's no shorter declaration for that in PHP. Handy that PHP uses untyped variables!
Usage:
a(2,3,10);
Returns:
2 5 8

You can save two bytes by omitting the final ?>.

PHP, 53
<?for(list(,$a,$n,$x)=$argv;$a<=$x;$a+=$n)echo"$a ";

R, 3 bytes
seq

Built in function with arguments from (a), to (top) and by (n)
usage seq(a,top,n) eg
seq(2,10,3)

output numeric vector
2 5 8

TI-Basic, 20
Prompt A,N,T:For(I,A,T,N:Disp I:End

Husk, 7 bytes
↑≤⁰¡+⁴²

Try it online!