x86 machine code, 13 bytes
This is basically a function that would be part of a device driver: it repeatedly reads the same address, so that should be an MMIO register for a PCIe device that accepts an input sequence. It outputs via port I/O to a specified port number (perhaps on the same PCIe device). Or more realistically, this runs in a VM where the hypervisor handles these streams. In C for the x86-64 System V ABI, void complement_sequence(int dummy, volatile int *input, uint16_t output_portnum) (except this is 32-bit code.)
IDK how justifiable it is to do binary I/O to MMIO and an IO port; it could save bytes incrementing pointers if used for finite challenges, and is not usable as a function on data in memory. But an infinite series requires I/O, if we pretend that 32-bit fixed-width integers didn't actually cap the input + output size as 4 x 2^32 bytes = 16 GiB, which x86-64 can easily handle. I don't plan to use this (or C volatile int*) for any finite challenges.
;; MMIO address in ESI for input
;; I/O port number in DX for output (or pointer in EDI for MMIO)
complement_sequence:
31C0 xor eax, eax ; start as if last value written or considered for writing was 0
; So we output (0, first_seq_num) non-inclusive on both ends
.next_seq:
8B0E mov ecx, [esi] ; next sequence number
A8 db 0xa8 ; opcode for test al, imm8 works like a forward jump by 1 byte ; jmp .entry
.write: ; do {
EF out dx, eax ; 1-byte instruction skipped on first iteration
.entry: ; entry point for first inner iteration
40 inc eax ; ++next_write
39C8 cmp eax, ecx
75FA jne .write ; } while(next_write != next_seq);
EBF5 jmp .next_seq
; no ret, we never return
Tested with a debugger locally, after replacing out with stosd and adding add esi, 4 after the load. Then I can pass it pointers to arrays in memory, and display (int[15])outbuf as I si in GDB.
Less golfed is 14 bytes, without the partial-instruction hack for loop entry skipping the 1-byte out dx, eax. The code above does that by using the opcode for a 2-byte test al, imm8 as equivalent to a 1-byte jmp forward, consuming the first byte as an immediate so it doesn't run on entry to the loop, only on subsequent iterations.
;; MMIO address in ESI for input
;; I/O port number in DX for output (or pointer in EDI for MMIO)
complement_sequence_less_golfed:
xor eax, eax ; start as if last value written or considered for writing was 0
; So we output (0, first_seq_num) non-inclusive on both ends
.next_seq:
mov ecx, [esi] ; next sequence number
jmp .entry
.write: ; do {
out dx, eax ; or mov [edi], eax for MMIO
.entry:
inc eax ; ++next_write
cmp eax, ecx
jne .write ; } while(next_write != next_seq);
jmp .next_seq
; no ret needed, this is a noreturn function
Algorithm: start with i = 0; (EAX)
- x = input from sequence (ECX)
for ( ; ++i != x ; ) { out(i); }- leave the loop with i == x, so i = previous sequence number.
- repeat, getting a new
x. (With i the same.)
This feels like a lot of jmp instructions, like maybe there's a better branch layout I'm not seeing. But with 2 nested loops, one of which might have run 0 iterations of part of the body, I guess this is reasonable.
intcan have anint sequence[1ULL<<31]array big enough to hold every positiveint. (In which case the output is the empty set). i.e. the length of a monotonic sequence of fixed-width integers is also finite. \$\endgroup\$volatile int *sourceand writevolatile int *sinkfor fixed-width 32-bitint. I guess in C you could hypothetically compile for an implementation whereintis arbitrarily wide, for any fixed problem size. But in x86 machine code for example, a type width of 32-bit really would be baked in to the answer. I assume this is still fine and sufficiently captures the spirit of the exercise, especially if you avoid a loop counter of some fixed width or array of fixed size.) \$\endgroup\$