text:
• ### Remove ads and support GameDev.net for only 3. Learn more: The New GDNet+: No Ads! • # Optimize 386/486/Pentium Code General and Gameplay Programming  --------------------------------- OPTIMIZE.TXT --------------------------------- Some useful informations about how to optimize code on a 386/486/Pentium This initially was a posting on the Internet made by Michael Kunstelj. Contact at : virteam@smoke.canberra.edu.au or mick@cairo.anu.edu.au Initially it included 486 and Pentium optimizations with some "holes" (like the profiling instructions), i filled the Pentium "holes" then refined some exaplanations (uh! maybe i made 'em worse! :} ). Then added some not-so-obviuos cache optimization techniques and other infos about specific optimizations you can make on 386. Lorenzo Micheletto N.B. I added some generic examples about how a cpu works BUT they are just examples, intel cpus work in slightly different ways. N.B./2 Always check in the books for things you are not sure there may be typos here. ---------------------------------- Brief intro about how a CPU works ---------------------------------- Now a brief intro on the innards Intel CPUs. Most processors these days have within in them a system termed a "pipeline". The 486 / 586 are certainly within this category. However, most people aren't quite sure what exactly a pipeline is, here follows a complete explanation: The execution of a machine code instruction can be roughtly split in five stages: [n.b. this is a generic pipeline] 1) FETCH instruction opcode and immediate data 2) DECODE opcode and align immediata data into temporary registers 3) CALCULATE ADDRESS OF OPERANDS and load 'em into memory. (calculate the address of memory locations to access and select the register operands to use) (sometimes called DECODE 2) 4) EXECUTE instruction (loading memory operands if needed) & write results to INTERNAL registers 5) WRITEBACK memory-operand results to memory Every stage takes ONE OR MORE cpu cycles to be completed, but usually a modern cpu needs just one cpu cycle for every execution stage (excluding stages 1 and 5 that have to deal with memory/cache access and stage 4 when "complex" microcoded instructions are executed). A cpu-core ( the "real" cpu, not cache support nor the other things that are usually integrated into a modern cpu) has five "specialized" units, one for every stage of instruction execution, plus a "register file" (and ultra-fast on-chip memory where internal register values are stored) and a CONTROL UNIT. The control unit "coordinates" the action of all the other units so they can work together. Here follows an extended ascii drawing of ONE on the many ways these units can be connected (use a ms-dos text editor to see this, or convert it to the Windows line-drawing character set if you are using a Windows editor): MEMORY INPUT ("memory load" unit) ? +------------+ +------->+------------+<-------->? ? +++ ? FETCH ? ? ? +---------------------+?+>+---------------+ ? ? ? (instruction pointer)? ? ? ? ? ? +------------+<-+ ? ? ? ? ? DECODE ?<-------->? ? ? ? +---------------+ ? ? ? ? ? ? ? ? ? +------------+<-+ ? CONTROL ? ? ++ ? ADDRESS C. ?<-------->? ? ? +----+-->+---------------+ ? UNIT ? ? ? ++ ? ? ? +------------------------+ +->+------------+<-+ ? ? ? REGISTER FILE +----->? EXECUTE ?<-------->? ? +------------------------+<---------------------+ ? ? ? ? ? +------------+<-+ ? ? ? WRITEBACK ?<-------->? ? +---------------+ ? ? ? +------------+ MEMORY OUTPUT <---+ ("memory store" unit) If you look the drawing, the control unit needs to communicate with all the other units to make 'em work together. Usually the "control unit" is scattered in little units that coordinates intruction and data flow between adiacent units, but you can think at it as a single indipendent unit. The five execution units are what gives the "raw" cpu power but the control unit is what lets you fully utilize 'em. Let's suppose every unit performs one operation in one step. With a "cheap" control unit, to execute a complete machine language instruction you first enable FETCH, then you enable DECODE and so on until WRITEBACK is completed and the control unit enables FETCH again to execute the next instruction. This is what happens into an "absolutely not pipelined" cpu with "one cycle" stages, the fastest instructions takes 5 cycles but the control unit is very simple (just a circular shift register that enables one unit at a time). Of course this is the worst case, nobody is so jerk to build a cpu like that. Every cpu stage-execution unit is a stand alone thing, it has its hardware and its "temporary registers" so it is capable to operate "alone". So, IF THE CONTROL UNIT can SINCHRONIZE the operations of all the stage-execution units, it can make 'em WORK IN PIPELINE (like in a factory, where every worker/robot in a production line a) receives a partially refined product from the previous worker in line b) performs some simple operations to refine the product a little more c) pass the result to the next worker in line ). A cpu with such a control unit is called a pipelined CPU. If you have to execute in sequence instructions A,B,C,D,E on a pipelined processor .... While the WRITEBACK unit is performing stage 5 of A the EXECUTION unit can perform stage 4 of B the ADDRESS CALCULATE unit can perform stage 3 of C the DECODE unit can perform stage 2 of D and the FETCH unit can perform stage 1 of E So if you start the cpu at instruction A it looks like that instruction A takes 5 cycles while instructions B,C,D,E (immediately one stage behind) looks like they take JUST ONE CYCLE!!! So if you execute a SEQUENCE of 8 instructions on a "not pipelined" processor with a five stage "pipe" it takes 40 steps to execute the sequence while on a pipelined processor this takes 5+7=12 steps!!! ( 5 steps for the first instruction to get thru the pipeline then 7 steps for the other instructions immediately "one step" behind) And the more instructions are executed in sequence, the more it looks like every instruction takes "just" one cycle to execute. This is of course the optimal situation, when the processor pipeline is filled and WHEN EVERY INSTRUCTION DOES NOT USE MEMORY/REGISTER OPERANDS "still under processing" IN SUCCESSIVE EXECUTION-STAGES!!!!!! ------------------------------------------------------------------------------- THINGS A CPU MUST CHECK TO MAKE A PIPELINE WORK CORRECTLY A pipelined processor control-unit must "check" : A) at stage 1 (FETCH) IF in stage 2..4 there are JUMP instructions [ they change the program counter (the same register used by the fetch unit) ] THEN stage 1 must "wait" until the jump is completed and then "restarts", loading the memory location pointed by the new program counter value. Because the jump opcode must pass thru the decode stage ... ... if the DECODE unit "detects" a jump opcode, it makes the FETCH unit "stops" AT LEAST for two cycles until the jump is performed. This of course means the processor pipeline "wastes" some cpu cycles. A 486 handles jumps in a smarter way, when the FETCH unit loads a jump instruction, it goes on assuming the jump WON'T BE TAKEN (it read the instructions following the jump). If the jump is taken, the values in the DECODE 1 and DECODE 2 units are "discarded" and the FETCH unit starts loading from the new program counter value. This explains why on 486 relative jumps (the fastest jumps) takes 3 cycles if taken (two cycles "lost") 1 cycle if not taken (no cycles lost) A "smarter" control unit can recognize in advance unconditional jumps and start immediately loading opcodes from the new program counter location AND/OR try to "predict" the jump destination of conditional jumps (like the Pentium does). B) at step 3 (ADDRESS CALCULATION) IF in stage 3 a register needed for address calculation is under processing in stage 4 (EXECUTE) THEN the stage 3 unit generates a "do nothing" control sequence for one cpu cycle. C) memory access conflicts These can be caused by lots of different things, they are usually resolved by the memory load/store units. Told in a short way, in a fully pipelined processor when the pipeline is "working on a sequence" the first instruction in the sequence takes the full execution time while the other instructions takes a shorter time (usually one cycle) because they are immediately behind, this means they "look faster" (and in fact they are, because the pipeline fully utilizes all the functional units it has). If some instructions "modify" values needed in the previous cpu stages the control unit stops the unit needing those values (and the others behind it) and inserts "do nothing" codes into the successive units in the processor pipe to make things work as expected (this is called a PIPELINE STALL or a PIPELINE FLUSH) This explains why usually a taken jump takes more time than one that's not taken (when a jump is performed you must flush the pipeline). The newer processors includes JUMP PREDICTION UNITS that handles jump faster, but the less you jump, the better. ------------------------------------------------------------------------------ PIPELINING IN INTEL PROCESSORS: The 386 is a "partially pipelined" processor with some optimizations. It checks for jumps ( A check) in a quite slow way and most of times can execute every stage in one cycle. It cannot perform the address generation check (B check) so it must execute stage 3 and 4 in "not pipelined mode". This explains why THE FASTEST 386 INSTRUCTIONS TAKE TWO CYCLES ( stage 3 unit must wait stage 4 to complete before managing the next instructions). The 486 has an improved EXECUTION unit (stage 4), improved memory access AND its control unit can perform the address generation check so that it can pipe stage 3 and 4 if there are no register/memory conflicts with two successive instructions. This explains why lots of 486 instructions take just one cycle (if the pipeline is filled and no pipeline stalls are produced). What's more, pipeline reloading is improved, so even jumps have less impact on execution time. It also has a 4Kbyte internal cache that boosts memory access and allows big gains from strip-mining optimizations. Another nice thing is the BURST READ access that accelerates memory reads when it needs to update its internal cache. PIPELINED,SUPERSCALAR & BRANCH PREDITING CPU: THE PENTIUM Well, what's beyound a fully pipelined processor like the 486 ? There is a 586/Pentium processor, that's SUPER SCALAR (more than one pipeline) and BRANCH PREDICTING (it has a specialized unit that annotates the position and the result of some og the most recent jumps, and so it can try to "guess" from where the next instruction after the jump execution will be loaded, if it guess correcly a pipeline stall is avoided, else it stalls)(this helps speeding up the execution of nested loops). The 586 can execute UP TO TWO integer operations in a single step (because it has TWO pipelines, but with some limitations) it can BURST READ/WRITE and has TWO indipendent 8k caches (Harvard style CPU to cache architecture) this means you can strip-mine to the max. if strips fit into the 8Kbyte data cache. Well, now you know how they work, let's see how to make 'em work to the max. ------------------------------------------------------------------------------ SPEEDING UP 486/586 CODE. ------------------------------------------------------------------------------ ------------------------------- ADDRESS GENERATION STALLS (AGI) ------------------------------- An Address Generation Interlock occurs when a register which is currently being used as the base or an index was the destination component of a previous instruction (the stage 3 to 4 pipeline stall i described above) For example,: add edx, 4 // AGI, ONE CLOCK STALL mov esi, [edx] For the 486, AGI's can only occur on adjacent instructions. On the 586 or Pentium instructions up to 3 locations away can cause an AGI. ( i.e. an instruction waiting to execute step 4 on pipeline 1 may need to wait the result produced by an instruction still executing on pipeline 2) pipeline step pipe1 pipe2 addres_calculate/fetch_operand C D | execute B A | V If C needs the results of A, it must stall pipeline 1 for one cycle to wait for A to "exit from" pipeline 2. If C needs the results of D, it must stall pipeline 1 for two cycles to wait for D to "exit from" pipeline 2. An example of 3 instruction away AGI: add esi, 4 pop ebx dec ebx mov edx, [esi] Takes 4 clocks on a 486. On a 586, the move command must wait for the add command, thus AGI stalling for one clock. The code above then would run in three clock cycles on a 586. Remember that even instructions that read or write implicitly to registers cause AGI stalls: mov esp,ebp pop ebp. is executed as... mov esp,ebp [agi] ; pop uses the esp as a pointer pop ebp ---------------------------- INSTRUCTION DECODING STALLS: ---------------------------- When decoding an instruction with an IMMEDIATE VALUE AND either an INDEX OFFSET or an IMMEDIATE DISPLACEMENT 486's have a one clock penalty. (586's do not) Example: mov spam, 248 mov dword ptr [esp+4], 1 This happens because the decode stage of the pipeline can read and decode ONE "immediate" value at a time while an immediate value and an immediate offset are TWO immediate values. The 586 instead has not such problems (when decoding) (execution is different) --------------------------------- REGISTER ACCESS CPU STALLS: --------------------------------- 486's have a 1 clock penalty when modifying the lower word of a DWORD register that's used immediately after it, 586's do not. Example: mov al,0 mov [ebp], eax (a one clock penalty on 486, no penalty on a 586) ------------------------------- CODE ALIGNMENT ------------------------------- To speed up the instructions, alignment of code should be on the beginning of cache boundaries. (32 bytes on 586, 16 bytes on 486) Thus, start your routine on the start of the cache page. This way, when someone calls the routine, the processor will just have to load a cache line to get the first sequence to feed into the pipeline, and while they are executing it will have enough time to load the other cache lines needed. This will speed up the processing of all the instructions within that page. The effect of this speed up on the 586 is not a dramatic as is it is on the 486 because the 586 has bigger caches and faster access to memory so a cache line load/store has less impact on cpu. ------------------------------ DATA ALIGNMENT ------------------------------ Misaligned access in the data cache causes an extra 3 cycles on both the 486 and 586. Ways to speed up data: For DWORD data, alignment should be on a 4-byte boundary. For WORD data, alignment should be on a 2 byte boundary for the 486, and simply within the 4-byte page for the 586. For 8 byte data (64 bits), data should be aligned on a 8-byte boundary so it is possible to use BURST READS (and burst writes too, on a Pentium). And yes, on many applications with tight inner loops, these things do accumulate to make a noticeable speed-up. ------------------------------------------------------------------------------- SPEEDING UP REGISTER AND OPERAND USAGE ------------------------------------------------------------------------------- Use the EAX as much as possible. Many instructions are 1 byte shorter when using EAX. That's less code you have to move around and slightly less internal processing. Use the DS register as much as possible for roughly the same reason, In the case of several references being made to a variable addressed with a displacement, load the displacement into a register. Try to use the ESP register to reference the stack in lower levels of your subroutines (faster than push/pop things and leaves EBP free for other uses) ------------------------------------------------------------------------------- HANDY INFO ON SPEEDING UP INTEGER INSTRUCTIONS ------------------------------------------------------------------------------- 1. Avoid using complex instructions like LEAVE, ENTER, LOOP, string instructions etc Simpler instructions will get the job done faster. Simpler instructions have been getting faster with every new processor that has come along. 2. With 8-bit operands, do your best to use the byte opcodes, rather than using the 32 bit instructions with sign and zero extended modes. Internal sign extension is expensive, and speed increases can be found by simplifying the process as much as possible. 3. LEA's generally increase the chance of AGI's. However, LEA's can be advantageous because: * In many cases an LEA instruction may be used to replace constant multiply instructions. (a sequence of LEA, add and shift for example) * LEA may be used as a three/four operand addition instruction. LEA ECX, [EAX+EBX*4+ARRAY_NAME] * Can be advantageous to avoid copying a register when both operands to an ADD are being used after the ADD as LEA need not overwrite its operands. The general rule is that the "generic" LEA A,[B+C*INDEX+DISPLACEMENT] where A can be a register or a memory location and B,C are registers and INDEX=1,2,4,8 and DISPLACEMENT = 0 ... 4*1024*1024*1024 or (if performing signed int operations) -2*1024*1024*1024 ... + (2*1024*1024*1024 -1 ) replaces the "generic" worst-case sequence MOV X,C ; X is a "dummy" register MOV A,B MUL X,INDEX ;actually SHL X, (log2(INDEX)) ADD A,DISPLACEMENT ADD A,X So using LEA you can actually "pack" up to FIVE instructions into one Even counting a "worst case" of TWO OR THREE AGIs caused by the LEA this is very fast compared to "normal" code. What's more, cpu registers are precious, and using LEA you don't need a dummy "X" register to preserve the value of B and C. 4. Zero-Extension with short ints terror tales The MOVZX takes four cycles to execute due to due zero-extension wobblies. A better way to load a byte into a register is by: xor eax,eax mov al,memory As the xor just clears the top parts of EAX, the xor may be placed on the OUTSIDE of a loop that uses just byte values. The 586 shows greater response to such actions. It is recommended that 16 bit data be accessed with the MOVSX and MOVZX if you cannot place the XOR on the outside of the loop. N.B. Do the "replacement" only for movsx/zx inside loops. 5. When comparing a value in a register with 0, use the TEST command. TEST operands by ANDing the operands together without spending any internal time worrying about a destination register. Use test when comparing the result of a boolean AND command with an immediate constant for equality or inequality if the register is EAX. You can also use it for zero testing. (i.e. test ebx,ebx sets the zero flag if ebx is zero) 6. Address Calculations Pull address calculations into load and store instructions. Memory reference instructions have 4 operands: a relocatable time segment base, a base register, a scaled index register and a displacement. Often several integer instructions can be eliminated by fully using the operands of memory addresses. (more on this later) 7. INTEGER DIVIDE In most cases, an Integer Divide is preceded by a CDQ instruction. This is as divide instructions use EDX:EAX as the dividend and CDQ sets up EDX. It is better to copy EAX into EDX, then arithmetic-right-shift EDX 31 places to sign extend. The copy/shift instructions take the same number of clocks as CDQ, however, on 586's allows two other instructions to execute at the same time. If you know the value is a positive, use XOR EDX,EDX. 8. INTEGER MULTIPLY The integer multiply by an immediate can usually be replaced with a faster and simpler series of shifts, subs, adds and lea's. As a rule of thumb when 6 or fewer bits are set in the binary representation of the constant, it is better to look at other ways of multiplying and not use INTEGER MULTIPLY. (the thumb value is 8 on a 586) A simple way to do it is to shift and add for each bit set, or use LEA. Here the LEA instruction comes in as major cpu booster, for example: LEA ECX,[EDX*2] ; multiply EDX by 2 and store result into ECX LEA ECX,[EDX+EDX*2] ; multiply EDX by 3 and store result into ECX LEA ECX,[EDX*4] ; multiply EDX by 4 and store result into ECX LEA ECX,[EDX+EDX*4] ; multiply EDX by 5 and store result into ECX LEA ECX,[EDX*8] ; multiply EDX by 8 and store result into ECX LEA ECX,[EDX+EDX*9] ; multiply EDX by 9 and store result into ECX And you can combine leas too!!!! lea ecx,[edx+edx*2] ; lea ecx,[ecx+ecx*8] ; ecx <-- edx*27 (of course, if you can, put three instructions between the two LEA so even on Pentiums, no AGIs will be produced). 9. Clearing Registers Using XOR reg,reg is fast but sets up conditions codes. A slightly slower way to do it of course is to mov reg,0 which preserves condition codes. 10. Avoid ENTER, instead, try something like: PUSH EBP mov ebp, esp sub esp, BYTE_COUNT 11. JUMP INSTRUCTIONS Jump instruction come in two forms, one real near that jumps between -127 and 128 of the current location, and a 32 bit version that does a full jump. The short form is quite a bit faster, however unfortunately many compilers put long jumps where short jumps would suffice. To ensure that short jumps can be used (when you know it is possible), explicitly specify the destination as being byte length (i.e use jmp short instead of plain jmp, if you can) 12. Task Switching Task Switching is evil. It is slow, real slow. Avoid task switching too often, as more and more of your time will be spent in processing the task switch. For faster task switching, perform you task switching in software. This allows a smaller processor state to be saved and restored. Anything that shaves time off 75+ clock cycles isn't all that bad in my book. 13. Minimize segment register loads and the use of far pointers as dearly much as you can. If you are doing a lot of processing on a small piece of data far away, it might be faster just to copy the data to nearby and work on it there (by the way, this is a good reason to use flat protected mode). ...and.... 14. THINK ABOUT WHAT YOU WANT TO DO All the other optimisations of Unrolling Loops, moving the invariant data etc still apply. That, however, is more an algorithmic problem for you, but still keep it firmly in mind. _______________________________________________________________________________ 586 Specific Optimizations ------------------------------------------------------------------------------- The 586Pent has a five stage pipeline structure. However, the pipeline is split into two different pipelines, known as Pipeline U and Pipeline V. This allows two instructions to be executed in parallel and thus presents the opportunity of executing two/instuctions per clock. The U pipeline is very much like the 486 pipeline, in that it can handle the entire set of instructions. Pipeline V on the other hand can handle only "simple" instructions. The fast parts of the U and V pipelines are possible as much of the functions are hardwired not microcoded. Anyway, I've blurted on about that for a bit, but what you want to know is "How to I get two instructions running in one clock/cycle?" Lament no further, here are the criteria: 1. Both instructions must be simple (see below) 2. There must not be a read-after-write or write-after-read register/flag dependencies between them. 3. Neither can have a displacement and an immediate 4. Instructions with prefixes can only occurr in the U-pipe (except for branches on condition jz,jc, etc.etc.) The following are considered "simple" instructions, the ALU means any ALU command (ADD etc): 1. Mov reg, reg/mem/immed 2. mov mem, reg/imm 3. ALU reg, reg/mem/immed 4. ALU mem, reg/immed 5. inc reg/mem 6. dec reg/mem 7. push reg/mem 8. pop reg 9. nop 10. lea reg/mem 11. Jmp/ Call / Jcc near N.B Remember only the U pipe can perform SHIFTS/ROTATIONS so "couple" every shift/rol with a simple instruction before and after to be sure every pipeline is filled. Note, however, than while both pipelines can perform ALU instructions concurrently, this is not the case when one ALU instruction requires the output of the other pipeline ALU instruction. Example: ALU instruction in pipe U and performing ADC in pipe V. There are two exceptions to this rule: 1) In the case of a compare/branch combination. 2) With push/pop combinations (because of optimized stack access) -------------------------- Branch Prediction ------------------------- Another nice optimisation with the 586 hardware is that whenever there is a possibility of a jump, for example, Jg, the 586 can automatically start "reading ahead" code from the jump location just in case the the Jump is accepted. Remember the CODE alignment thing above? Well, it couldn't hurt your grandmother to align the labels on the code pages. ------------------------------------------ Amazing new 586 Optimizations and speedups ------------------------------------------ The 586 has a lot of really nice optimizations and kick-ass features in addition to what I've mentioned above, unfortunately, this information is proprietary and will only be given to people who sign non-disclosure agreements and shell out a\$ or two...  Bummer...
(Meethinks, 586 clone-makers won't be too happy about that... :-) )
Compiler/OS makers will probably be the purchasers.
Quite a few of these optimisations won't work on anything less than
a 586, so don't sweat too much about it.  Hey, just write
for 386/486/586 and you'll be ok.

Hovewer, i found a nice article on July 1994 Byte about some
"secret weapons of Pentium coders"....

============================================================================
PENTIUM'S PROFILING REGISTERS:

Pentiums have a set of 64bit "machine specific registers" (MSR)
that are accessed by way of the RDMSR (read MSR) and WRMSR (write MSR)
instructions.

THESE ARE PROTECTED MODE, RING 0 INSTRUCTIONS (CPU LEVEL 0)
( can work in a 386Powered programs only if executing under VCPI
XMS or "no V86 manager"
or if you find a way to "toggle" DPMI from ring 3 to ring 0)
(I think they can work even if you boot ms-dos in real mode
and use the proper instruction prefixes needed to execute
32bit instructions in real mode).

-----------------------------------------------------------
Copies the MSR register indexed by ECX
into the 64bit pair  EDX:EAX

RDMSR macro
db 0Fh,032h
endm
-----------------------------------------------------------
WRMSR   Write MSR
Copies into the MSR register indexed by ECX
the value contained into the 64bit pair  EDX:EAX

Macro to insert it into code if your assembler
does not support Pentiums:

WRMSR macro
db 0Fh,030h
endm
-----------------------------------------------------------

Intel Pentium user manuals, documents only MSR 0, 1 and 0Eh
and states that MSR 3, 0Fh and above 13h are reserved and illegal.

So, what's left? And what's useful to you ?

MSR 10h is the counter of CPU CYCLES since last power-up.
That value can also be read with the RDTSC (Read time stamp counter)
instruction)
RDTSC is 0Fh,031h in bytes and must be executed while in ring 0 too.

MSR 10h is the most precise timer available on the Pentium
because it "ticks" at the CPU frequency.

Then comes MSR 11h,12h and 13h there you will find the hot stuff

The lower 32bits of MSR 11h are actually two INDEXES
INTO THE CPU PROFILING REGISTERS!!!!

The profiling registers are CPU EVENT TIMERS AND COUNTERS
they can keep track of what's going on inside and outside
your super-duper processor, they can detect nearly everything the CPU does.

The first 16bits of MSR11h selects
the profiling register accessible thru MSR 12h.
The second 16bits of MSR11h selects
the profiling register accessible thru MSR 13h.

Here comes the format of the "profiling register indexes":
bit 0..5 : type of the profiling register to access
bit    6 : Set if you want to monitor the events in cpu ring 0,1,2 (system)
bit    7 : Set if you want to monitor the events in cpu ring 3 (user level)
bit    8 : 0 = access count-of-hardware-events
1 = access count-of-total-cpu-cycles used to process the cumulated
events.
(i'm not sure of this, maybe 0 means count time and 1 count events)
bit 9..15: UNKNOWN, DO NOT MODIFY

Profiling registers types:
INDEX  NAME
0       data write
2       data TLB miss (translation look-aside buffer)
4       data write miss
5       write (hit) to M or E state lines
6       data cache lines written back
7       data cache snoops
8       data cache snoop hits
9       memory accesses in both pipes
0Ah     bank conflict
0Bh     misaligned data memory reference
0Dh     code TLB miss
0Eh     code cache miss
10h     ????
11h     ????
12h     branches
13h     BTB hits  (Branch Target Buffer)
14h     taken branch OR BTB hit
15h     pipeline flushes
16h     instructions executed
17h     instructions executed in V-pipe
18h     bus utilization (clocks)
19h     pipeline stalled by write backup
1Ah     pipeline stalled by data memory write
1Bh     pipeline stalled by write to E or M line
1Ch     locked bus cycles
1Dh     i/o read or write cycles
1Eh     non cacheable memory references
20h     ????
21h     ????
22h     FPU operations
23h     breakpoint 0 match
24h     breakpoint 1 match
25h     breakpoint 2 match
26h     breakpoint 3 match
27h     hardware interrupts
28h     data read or data write
29h     data read miss or data write miss

So if you want to profile things:
0) Set properly the environment of the test
(cache empty, cache filled with all the routine code, etc. etc.)
1) Set MSR 11h to the two counters you want to read
2) Read MSR 12h,13h to get the initial values,
3) Execute the code you want to profile
4) Read the final values of MSR 12h,13h
(without setting MSR 11h again this time).
5) Calculate the difference between the initial and final values.

This way if you are not sure how to optimize things
you can actually test how they work and what's going on.

USING THE PROFILING REGISTER YOU CAN "TEST ON THE ROAD"
YOUR CODE DOWN TO THE LAST CPU CYCLE!!!!!

-------------------------------------------------------------------------------
386 Optimization
-------------------------------------------------------------------------------

Well, nobody buys a 386 now, right?
But still lots of people has one....
So if you wanna be 386 friendly remember .....

--------------------------
--------------------------

When a jump is performed, a 386 spends some extra time decoding
the next instruction to execute and flushing the pipeline.

THE FIRST INSTRUCTION requires exactly ONE EXTRA CPU CYCLE
for every COMPONENT ( prefixes, opcode, mod/rm , sib ,offset, immediate value )
of the instruction.  Notice i said COMPONENT!!!
An 8bit displacement or a 32bit one, count always as an 1 extra cycle.

So, in 32bit mode (where no prefixes are needed for 32bit instructions):

loopme: inc esi              ; opcode
mov [edi+1234h],eax  ; opcode, mod/rm , immediate offset
dec ecx              ; opcode
jne short loopme     ; opcode short_displacement

IS FASTER THAN:

loopme: mov [edi+1234h],eax
inc esi
dec ecx
jne short loopme

Because placing first the three component mov instruction
adds 2 cycles to the instruction execution time, weird, uh?
But if you remember this thing, you can boost 386 code a lot.

By the way, remember that "pipeline overhead" is not so obvious to calculate.
Look at this:
stosd         ; opcode    <--- these "slow" instruction pipes-in faster
pop eax       ; opcode    <--- so if you can, put 'em first

------------------
SHORT INSTRUCTIONS
------------------

Short instructions are loaded and decoded faster than longer ones
and since 386 has no internal cache and less memory access bandwidth
than a plain 486, this helps a lot.

Well that's all for a 386.

-------------------------------------------------------------------------------
CACHE OPTIMIZATION TECHNIQUES  (THEY CAN WORK ON ANY CPU!!!!!!!!!!!!)
-------------------------------------------------------------------------------

Usually "code optimization" is cpu-based, but there more things
up in the sky and down on earth than just a cpu... the cache for example!

Well, the difference between a cache hit and a cache miss
means lots of cpu cycles lost, so better hit the cached locations to the max.

386 usually have and external 64k ... 128k cache (mine has none, sigh! :( )
486 have a 4k internal cache and a 64k...512k (usually 256k) second level cache
Pentiums have an Harvard 8k code + 8k data cache
plus a 256k..1Mbyte second level cache.

Use "short" loops so there is more probability that the code to execute
will reside fully into the cache.

Then remember you can count on an external cache of at least 64k
(usually 128k..256k for a 486).

So, if you have to process big arrays or big bitmaps with multiple passages
do not "scan" all the array for every pass, use a "strip by strip"
strategy instead so every "strip" fully fits into the cache
and is ready for the second and third pass without cache misses.

This technique is called STRIP-MINING, you can include into your program
a routine that checks the optimal "strip size" trying a multi-pass test
on 64k,128k,256k,512k strips and "complete array"
and then sets the optimal "strip size" to use
when perfoming "strip-mining" routines.

On a Pentium you can use 8k "strips" so your "strip mined" routines
will work with the full speed of the internal data cache
(remember the internal cache works at full cpu speed while
the secondary cache may be runnin at half that).

The advantage of strip mining is caused by the fact that
the additional jumping/looping needed to process arrays in "strips"
of adiacent memory locations that can fit together into the cache
is A LOT LESS than the time caused by a single cache miss.

-------------------------------------------------------------------------------
NOT SO OBVIOUS OPTIMIZATIONS
-------------------------------------------------------------------------------

----------------------
COMPLEX INSTRUCTIONS
----------------------
Intel says complex instruction are evil on 486 and up, but there are
exceptions... expecially if want to make things run smooth on 386 too.

STRING instructions are FASTER on 386, expecially if they are the first
in a loop.

If you have to move data in 32bit chunks you'd better use REP MOVSD if you can
because it alone replaces this "simple instructions only"
super-optimized sequence:

rep_loop:
mov eax,[esi]
mov [edi],eax
dec ecx
jne rep_loop

REP MOVSD takes  2+7*n cycles on a 386 or 486

While the "optimized" sequence uses EAX
and takes [(2+4+2+2+2+2+7)*n - 4 ] = [21*n - 4] cycles on a 386
and [  (1+1+1+1+1+3)*n - 2 ] = [ 8*n - 2] cycles on a 486

Cache-line aligning the "optimized" code on a Pentium
i think it takes  [ 3*n ]  cycles.
So if 486s are your base system don't throw away REP MOVSD

Also remember that REP MOVSD take 2 bytes instead of 13 bytes
does not need to use EAX (one more register free for other things)
and it does not use the Pentium's BTB (Branch Target Buffer)
so you can be sure it does not miss and the outer loops
with entries in the BTB can be one level deeper.

What's more, the AMD K5 automatically splits a complex instruction
into an optimized sequence of simple instructions
and issues them to fully utilize the four execution units it has.
Guess what it means for poor old movsd :)

Heck! I think those Intel engineers lost a big thing when they
decided to not improve MOVS/LODS/STOS. A "blitter" unit directly
controlled by string instructions (with "fetch ahead","bufferize"
and "auto align" capabilities) could be a great thing for us.

a "head" byte move (to align things)
a "central" qword move (burst read/burst writes)
and a "tail" byte move (to align things).
And all this without trashing the processor data cache!!!!
Can you immagine the boost your code may get?
Heck! Sun engineers ADDED "blitter" support in their new 64bit sparc cpus
because they seen their software moving data a lot, why Intel ones did not?

On a Pentium you can get the optimal 2-cycle memory to memory MOV
by way of pipelining, but this cannot take advantage of the fact
that when performing REP MOVS the processor KNOWS AHEAD how many locations
will be moved (read: on a "smarter" cpu this can help optimize to the
max the processor-to-memory bandwidth and avoid caching overhead)
nor it can take advantage of the full power of burst read/writes
neither it can take advantage of the fact that WHILE THE STRING MOVE
IS GOING ON, the processor pipelines can execute OTHER instructions after
the MOVS and "not dealing" with the memory range "under transfert"
or with ECX,ESI,EDI and Direction Flag.
I hope they will take note of this for P7.

-------------------------------------------------------------
-------------------------------------------------------------
Don't be fooled by the current Riscy trend, be cooler than the rest.
Some Intel "complex addressing" modes are really powerful
if you just have enough creativity.
Lets suppose you need to add together data from "four"
streams of data....

A riscy (risc-like) way to do this could be...
; 486 timings when looping
riscy_way:
mov eax,[esi]  ; 1
mov [edi],eax  ; 1
dec ebp        ; 1
jne riscy_way  ; 3
; loop cycles = 17

Now lets see the "intelly" way! :)
Let's suppose the "counter" EBP won't exceed 2^31 -1
we can do the following ...

lea esi,[esi+ebp*4]
lea edx,[edx+ebp*4]
lea ebx,[ebx+ebp*4]
lea ecx,[ecx+ebp*4]
lea edi,[edi+ebp*4]
neg ebp ; negate increment
; then you can fully use the address unit ALU

; 486 timing when looping
intelly_way:
mov eax,[esi+ebp*4]  ; 1
mov [edi+ebp*4],eax  ; 1
inc ebp              ; 1
jnz intelly_way      ; 3
; loop cycles = 12

On a Pentium, "riscy" and "intelly" runs at nearly the same speed
BUT ON A 486, the "riscy" way runs 30% slower than "intelly" !!!!

This means that using the "riscy" code
your 486 will look like a slow cow compared to a Pentium
while using the "intelly" code your 486 will look good enough
( not to mention this helps to make the difference between
"needs a Pentium" and "this flies on 486 too!!").

-------------------------------------------------------------
32bit ACCESS SPEAKS FOR ITSELF, just remember to fully use it
-------------------------------------------------------------

Everywhere you can, use 32bit instructions
and if you can, align data on 32bit.

For example, let's say you have to manipulate lots of strings,
if you align them on dword boundaries (including string lenght)
with null byte paddings, you can boost processing time MORE THAN 8 TIMES!!!!

The same thing applies to manipulating 8bit bitmaps and "software" sound mixing.

Into 386mixer coded a routine that mixed simultaneously 4 sound channels
running only on internal register and mixing up to 4 samples at a time
from the 4 channels (look at the "intelly" example above).

If you need speed, you can even tollerate small calculation errors
or reduced precision
and manipulate successive 8,16bit values in a single 32bit instruction.

Let's say you have and array of unsigned words and you need to multiply them
for a constant, say 45, how can you do that ?
If you know the values won't overflow the 16 bit they use
(if they overflow you will have to choose another method), you can do the
following:
mov ecx,count
handle_two_words:
mov eax,[esi] ; load two words at a time
; an AGI happens, but i can't eliminate it
lea eax,[eax+eax*4]  ; multiply by 5
add esi,4  ; increment pointer, avoid 486 AGI
; reduce by 1 the Pentium AGIs
lea eax,[eax+eax*8]  ; then multiply by 9
dec ecx  ; decrement counter & keep Pentium at full power
mov [esi],eax   ;
jne handle_two_words

And if you have very big arrays, you can even unroll two or three times
the loop to further speed up this code.

------------------
SELF COMPILED CODE
------------------

Sometimes you need to execute lots of times the same "jump filled"
instruction sequence, and you know ahead what jumps will be taken
and what won't.
What's worse if there are lots of conditional jumps (Jcc) "in sequence"
they may be enough to overflow the capability of branch-prediction units!!!

So, what can you do?
My answer to this is a SELF-COMPILER!!!
A small finite state machine that instead of crunching data directly
IT GENERATES SUPER-SPECIALIZED ROUTINES that will crunch the data in the
fastest way the code generator knows.

I've done a thing like that for the _PageFLip1 routine in 386video.asm.
At mode initialization a code generator generates
all the 256 blit-skip sequences the _PageFLip1 routines may need
when copying "modified" pixels on screen.

This way a call is performed only after 32 blitted pixels, instead of jumping
every 2..4 pixels (or every pixels in the worst case situations).

By the way, this is NOT self-modifying code
this is an "integrated code compiler".

------------------------------------------------------------------------------
I hope this information has been helpful for you.
Now make some coffee, brush your teeth and phone up your girlfriend and
go and see a movie.   This document will be here when you get back, and I
imagine there is only so much of this you can take in one day.... :-)  :-)  :-)

Live long and code well...

Regards,

Michael Kunstelj.

Regards from me too,

Lorenzo Micheletto

Report Article

## User Feedback

There are no comments to display.

## Create an account

Register a new account

• 0
• 0
• 1
• 1
• 3

• 9
• 12
• 9
• 33
• 13


text:
7 years, 40 days

## @Carl Love yes, works now just fine...

@Carl Love yes, works now just fine.

## @vv , it doesn't seem to be working...

@vv , it doesn't seem to be working.

I get the following error message:

Error, pds does not evaluate to a module

## @Carl Love here's my third try: &nb...

@Carl Love here's my third try:

 > restart;   PDE := diff(u(x, t), t) = diff(u(x, t), x, x)+sin(x+t)-cos(x+t);   IBC:= D[1](u)(0,t)=sin(t),         D[1](u)(1,t)=-0.000065*(u(1, t)+cos(1+t))^4+sin(1+t),         u(x,0)=1-cos(x); # # For x=0..1, t=0..1, the solution varies only very slowly # so I have increased the timestep/spacestep, just to speed # up results generation for diagnostic purposes #   pds := pdsolve( PDE, [IBC], numeric, time = t, range = 0 .. 1,                   spacestep = 0.1e-1, timestep = 0.1e-1,                   errorest=true                 )
 (1)
 > # # Plot the solution over the ranges x=0..1, # time=0..1. Not a lot happens! #   pds:-plot(x=1, t=0..1);
 > # # Plot the estimated error over the ranges x=0..1, # time=0..1 #   pds:-plot( err(u(x,t)), x=1,t=0..1);
 > # # Get some numerical solution values #   pVal:=pds:-value(u(x,t), output=procedurelist):   for k from 0 by 0.01 to 1 do       pVal(1, k)[2], pVal(1, k)[3];   od;
 >
 (2)
 >
 > restart;   PDE := diff(v(x, t), t) = diff(v(x, t), x, x);   IBC:= D[1](v)(0,t)=0,         D[1](v)(1,t)=-0.000065*v(1, t)^4,         v(x,0)=1; # # For x=0..1, t=0..1, the solution varies only very slowly # so I have increased the timestep/spacestep, just to speed # up results generation for diagnostic purposes #   pds1 := pdsolve( PDE, [IBC], numeric, time = t, range = 0 .. 1,                   spacestep = 0.1e-1, timestep = 0.1e-1,                   errorest=true                 ); # # Plot the solution over the ranges x=0..1, # time=0..1. Not a lot happens! #   pds1:-plot(x=1, t=0..1);
 >
 >

## @tomleslie here's the code:   ...

@tomleslie here's the code:

## @Preben Alsholm thanks. BTW do you ...

@Preben Alsholm thanks.

BTW do you know why did the collocation code you wrote doesn't seem to work for n:=91 and T:=[seq(0.1..1,0.01)];?

Did you try to excute the code in your machine with the change above that I changed?

I appreciate your help, but I would like to use collocation method, so I am puzzled why it's get stuck on what I changed.

## @Preben Alsholm ,I want to use 100 ...

@Preben Alsholm ,I want to use 100 points for the precision on the accuracy of the numerical solution.

My colleague told me that 10 points of sampling isn't enough for what we want to account for.

## @Preben Alsholm , if I want to use ...

@Preben Alsholm , if I want to use 100 points, I need to change n:=100 and T:=[seq(0..1,0.01)];

I changed half an hour ago to n:=91 and T:=[seq(0.1..1,0.01)]; in the code and the code still evaluates on maple 18, is there a way to shorten the computation time?

One of my colleagues told me that something is wrong in the code if it takes that much time to evaluate?

## @Preben Alsholm how do I find the n...

@Preben Alsholm how do I find the numerical values of the approximated solution at the collocation points?

## @Preben Alsholm For my problem I ca...

@Preben Alsholm For my problem I can use the following discretization scheme:

If we take time steps x_i = ih, y_j = jh, then:

1/h^2(-u_{i,j-1}-u_{i-1,j}+4u_{i,j} - u_{i+1,j} - u_{i,j+1}) = \sqrt(u_{i,j}) + (u_{i+1,j}-u_{i-1,j})^2/(4h^2 * u_{i,j}^{3/2}

But how to implement this in maple?

Thanks.

## @Preben Alsholm , how can I plot th...

@Preben Alsholm , how can I plot the error of this approximated solution?

@Carl Love u(x1,x2,x3,x4) satisfies: d^2u/dx1^2+d^2u/dx2^2 = d^2u/dx3^2+d^2u/dx4^2

and u is twice differentiable.

## error estimate....

@Preben Alsholm , hi, do you happen to know how can I estimate the error in this numerical solution?

## response...

@Preben Alsholm , this is another recursive integral equation which I want to solve numerically, I thought I could do it by using maple.

## the recursion...

@Axel Vogt t>0, we can also truncate it to t<1.

## @tomleslie  Thanks, I appreciate yo...

Thanks, I appreciate your time you spent on this.

format: plain


text:
# Races and Circular Tracks

Adam and Bob are running on a circular track of circumference 1500 m. They start simultaneously from point A in the same direction. Ratio of their speeds is 5:3 respectively. If they keep running , then at how many different points can they meet?

a)Two b)One c)Three d)Data Insufficient

-
Hint: convert $1500\ m \rightarrow 2\pi$ and work some trigonometric magic. The two runners meet when the difference in their phases ($5t-3t$) is a multiple of $2\pi$. You still have to find all positions, however...


text:
# The upper half of an inclined plane of inclination $\theta$ is perfectly smooth while the lower half is rough.A block starting from rest at the top of the plane will again come to rest at the bottom if the coefficient of friction between the block and the lower half of the plane is given by
$\begin{array}{1 1}\mu=2\tan\theta\\\mu=\tan\theta\\\mu=\large\frac{2}{\tan\theta}\\\mu=\large\frac{1}{\tan\theta}\end{array}$


text:
# I'm having trouble putting some parameters in the naive Bayes algorithm into comprehensive terms

https://app.dataquest.io/m/432/the-naive-bayes-algorithm/3/using-bayes-theorem

I was wondering if anyone could help me put this into layman’s terms. I understand the trick on how to apply the calculations to reach the desired result but I do not exactly get what the 3 “new_message” parameters mean (see below).

I understand that the probability of a new message being spam or non spam both equal 0.5. What I do not understand is what the p_new_message means.

‘’’
p_spam = 0.5
p_non_spam = 0.5
p_new_message = 0.5417
p_new_message_given_spam = 0.75
p_new_message_given_non_spam = 0.3334
‘’’

My unconfirmed assumptions are:

p_spam = P of any new message being spam
p_spam = P of any new message not being spam
p_new_message = P of a new specific message being spam based on its contents
p_new_message_given_spam = P of this message having been correctly assigned to spam
p_new_message_given_non_spam = P of this message having been correctly assigned to non spam

Sorry I’ve been posting many questions lately…

1 Like

No, that would be incorrect. P(x) is not a conditional probability. It is just the probability of x.

In this case, x is New Message. So, P(New Message) is just the probability of whether a new message has arrived.

2 Likes

p_spam: Is the probability that a message is spam. In this case, half of the messages received are spam messages

p_non_spam: Is the probability that a message is not spam. p_non_spam = 1 - p_spam when they are mutually exclusive and exhaustive

p_new_message : Is the probability of getting a new message and it is equals p_non_spam * p_new_message_given_non_spam + p_spam * p_new_message_given_spam

p_new_message_given_spam: Is the conditional probability that a new message is spam

p_new_message_given_non_spam: Is the conditional probability that a new message is non spam

If I remember correctly, p_spam and p_non_spam are called prior probabilities. This is the probability that you have before your experiment.

2 Likes

Thank you for your quick answer. Tho I’m still unclear about the Importance for a spamfilter to know the probability of a new message arriving? Would it not just arrive or not arrive?

Is a new message only a new message when its uniquely different to another? In other words is a duplicate message not counted as a new message?

2 Likes

Thank you for elaborating! However it doesn’t click for me why two mutually exclusive and exhaustive probabilities have a combined P higher than 1 in their conditional state tho.

p_new_message_given_spam = 0.75
p_new_message_given_non_spam = 0.3334

1 Like

Your conditional probabilities are dependent on other events happening. So they do not sum up to 1.

1 Like

But if two probabilities add up to more than P = 1 it must mean that an outcome can be in both states. Therefore both non-spam and spam at the same time. Since P can never be larger than 1 when mutually exclusive, correct?

1 Like

You do not sum conditional probabilities.

Probabilities that are not conditional sum up to 1.

1 Like

Hi, I still don’t see the sense in having the probability of getting a new message.

A spam filter should assess whether a message that has arrived is spam or not, so probability of a new message having arrived should always be 1.

Yes, you can derive this quantity using the formula you stated, but this doesn’t confirm its physical meaning.

1 Like

@pgfox96

The probability of new message is the sum of the probabilities of getting a non_spam and a spam message.

I would recommend Chapter 13: Naive Bayes in Data Science from Scratch by Joel Grus.

2 Likes

Sorry but that still doesn’t answer my question.
Look at this screenshot, from the ‘Instructions’ for Screen 3.

Now if a new message has been received, then why does:

P(New message) = 0.5417?

The message has been received! It makes no sense to talk of the ‘probability of getting a new message’, as you said in your first response.

Is there something I am not understanding? Any help would be much appreciated.

1 Like

@pgfox96

If you applied the formula for p_new_message above you will get 0.5417.

This is how Naive Bayes works. The probability of new_message is the same as getting the probability of delay in this mission

p_delay = p_boeing*p_delay_given_boeing + p_airbus*p_delay_given_airbus

If you agree with the above, please apply similar understanding.

Cheers!

1 Like

Hey folks, sorry to see this is causing confusion!

P(\text{New Message}) doesn’t mean the probability that a new message has arrived. When a message arrives, the probability that it arrives is always 1.

\text{New Message} is a variable name that takes concrete values in concrete cases. For instance, if the new message is “Urgent!!!”, then P(\text{New Message}) = P(\text{"Urgent!!!"}).

If the new message is “Hey Tom, are u home?”, then P(\text{New Message}) = P(\text{"Hey Tom, are u home?"}).

5 Likes

I think that going back to a chart like this might be helpful to visualize what is going on.

The outermost box represents the ratio of all messages being either spam or not spam. This is our prior probability. In this case, we get a new message and without looking at contents of the message at all, we are told the message has a .5 probability of being spam and a .5 probability of being not-spam so the box is simply divided in half.

Next, we are told that  P(new message) = .5417. What does this mean??? This is the probability, as determined by our algorithm, that this message is spam . This is the area of the chart that is pink.

And finally, we are told

P(new message | spam) = 0.75
P(new message | not-spam) = 0.3334

We can think of this as saying, 75% of the spam side tests as spam and is pink, and 33% of the not-spam side also tests as spam and is pink. This is the posterior probability. Note that these DO NOT add up to 1 or 100%. However,

P(new message | spam) + P(not-new message | spam) = 1
P(new message | not-spam) + P(not-new message | not-spam) = 1

The questions for this lesson ask us to calculate what ratio of the pink is on the spam side, and what ratio is on the not-spam side.


text:
Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

C. Prairie Partition
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

It can be shown that any positive integer x can be uniquely represented as x = 1 + 2 + 4 + ... + 2k - 1 + r, where k and r are integers, k ≥ 0, 0 < r ≤ 2k. Let's call that representation prairie partition of x.

For example, the prairie partitions of 12, 17, 7 and 1 are:

12 = 1 + 2 + 4 + 5,

17 = 1 + 2 + 4 + 8 + 2,

7 = 1 + 2 + 4,

1 = 1.

Alice took a sequence of positive integers (possibly with repeating elements), replaced every element with the sequence of summands in its prairie partition, arranged the resulting numbers in non-decreasing order and gave them to Borys. Now Borys wonders how many elements Alice's original sequence could contain. Find all possible options!

Input

The first line contains a single integer n (1 ≤ n ≤ 105) — the number of numbers given from Alice to Borys.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1012; a1 ≤ a2 ≤ ... ≤ an) — the numbers given from Alice to Borys.

Output

Output, in increasing order, all possible values of m such that there exists a sequence of positive integers of length m such that if you replace every element with the summands in its prairie partition and arrange the resulting numbers in non-decreasing order, you will get the sequence given in the input.

If there are no such values of m, output a single integer -1.

Examples
Input
81 1 2 2 3 4 5 8
Output
2
Input
61 1 1 2 2 2
Output
2 3
Input
51 2 4 4 4
Output
-1
Note

In the first example, Alice could get the input sequence from [6, 20] as the original sequence.

In the second example, Alice's original sequence could be either [4, 5] or [3, 3, 3].


text:
# zbMATH — the first resource for mathematics

The minimal normal extension for $$M_ z$$ on the Hardy space of a planar region. (English) Zbl 0704.47019
Let $$S=M_ z$$ be the subnormal operator defined by multiplication by the independent variable on $$H^ 2(R)$$, the space of analytic functions f on a bounded open region R in the complex plane such that $$| f|^ 2$$ has a harmonic majorant. This paper characterizes the minimal normal extension N of S. As it is known, any normal oprator is determined by a scalar-valued spectral measure and a multiplicity function. In our case the scalar-valued spectral measure for N is a harmonic measure $$\omega$$ for R. The author investigates the multiplicity function m for N. It is shown that m is bounded above by 2 $$\omega$$-a.e., and necessary and sufficient conditions are given for m to attain this upper bound on a set of positive harmonic measure. Interesting examples are discussed which indicate the relationship between N and the boundary of R.
Reviewer: M.Martin

##### MSC:
 47B20 Subnormal operators, hyponormal operators, etc. 31A15 Potentials and capacity, harmonic measure, extremal length and related notions in two dimensions
Full Text:


text:
## Testing Hamiltonicity (and other problems) in Minor-Free Graphs

by Reut Levi and Nadav Shoshan

As stated in the Feb'21 news of PT Review, although testing grqaph properties has been studied extensively in the dense graph model (see Chap 8 of my Intro to PT) and quite extensively in the bounded-degree graph model (see Chap 9), the general graph model (see Chap 10) has been studied much less. In particular, as reviewed in Section 1.2.3 of the current paper, most of the known results refer to inputs that are promised to be of a restricted form (e.g., be minor-free), and the current paper continues this line of research.

The main results, in my opinion, are the tester of Hamiltonicity and the local construction of an almost minimum weight spanning subgraph in minor-free grqaphs, in the general graph model. These \$\poly(1/eps)\$-query algorithms use the new partition oracle of Kumar, Seshadhri, and Stolman. Note that, although these oracles assume that the graph has bounded degree, they can be used in the current setting by effectively ignoring the few vertices of high degree.

In addition, this work presents improved testers for the bounded-degree graph model, while also assuming that the input graph is minor-free. These the improvements are obtained by using a relaxed notion of partition oracles, which suffices for the foregoing applications, and allows for a simpler and more query-efficient implementation.

#### The original abstract

In this paper we provide sub-linear algorithms for several fundamental problems in the setting in which the input graph excludes a fixed minor, i.e., is a minor-free graph. In particular, we provide the following algorithms for minor-free unbounded degree graphs.

• A tester for Hamiltonicity with two-sided error with poly(1/eps)-query complexity, where eps is the proximity parameter.
• A local algorithm, as defined by Rubinfeld et al. (ICS 2011), for constructing a spanning subgraph with almost minimum weight, specifically, at most a factor (1+eps) of the optimum, with poly(1/eps)-query complexity.
Both our algorithms use partition-oracles, a tool introduced by Hassidim et al. (FOCS 2009), which are oracles that provide access to a partition of the graph such that the number of cut-edges is small and each part of the partition is small. The polynomial dependence in 1/eps of our algorithms is achieved by combining the recent poly(d/eps)-query partition oracle of Kumar-Seshadhri-Stolman (ECCC 2021) for minor-free graphs with degree bounded by d.

For bounded degree minor-free graphs we introduce the notion of covering partition oracles which is a relaxed version of partition oracles and design a poly(d/eps)-time covering partition oracle for this family of graphs. Using our covering partition oracle we provide the same results as above (except that the tester for Hamiltonicity has one sided error) for minor free bounded degree graphs, as well as showing that any property which is monotone and additive (e.g. bipartiteness) can be tested in minor-free graphs by making poly(d/eps)-queries.

The benefit of using the covering partition oracle rather than the partition oracle in our algorithms is its simplicity and an improved polynomial dependence in 1/eps in the obtained query complexity.

Back to list of Oded's choices.


text:
# CTAN update: longdivision

Date: March 26, 2019 10:49:20 AM CET
Hood Chatham submitted an update to the longdivision package. Version number: 1.1.0 2019-03-24 License type: lppl Summary description: Long division arithmetic problems Announcement text:
Updated to include more flexible output, including partial completion of a problem, "German" style long division, a nicer radical symbol if tikz is loaded, and various notations for repeating decimals.
Thanks for the upload. For the CTAN Team Erik Braun
We are supported by the TeX users groups. Please join a users group; see http://www.tug.org/usergroups.html .

## longdivision – Typesets long division

This package executes the long division algorithm and typesets the solutions. The dividend must be a positive decimal number and the divisor must be a positive integer. Repeating decimals is handled correctly, putting a bar over the repeated part of the decimal. Dividends up to 20 digits long are handled gracefully (though the typeset result will take up about a page), and dividends between 20 and 60 digits long slightly less gracefully.

The package defines two macros, \longdivision and \intlongdivision. Each takes two arguments, a dividend and a divisor. \longdivision keeps dividing until the remainder is zero, or it encounters a repeated remainder. \intlongdivision stops when the dividend stops (though the dividend doesn’t have to be an integer).

This package depends on the xparse package from the l3packages bundle.

 Package longdivision Version 1.2.0 2020-05-09 Maintainer Hood Chatham

more


text:
## tterbecki Group Title A 60-kg man standing on a scale in an elevator notes that as the elevator rises, the scale reads 819 N. What is the acceleration of the elevator? one year ago one year ago

1. imron07 Group Title

$\Sigma F_{up}=ma\\ N-mg=ma\\a=\frac{N-mg}{m}$ Whwre N is the scale reading.

2. Decart Group Title

he is correct n = 819

3. tterbecki Group Title

so then mg is 60 how do i get m?

4. Decart Group Title

mg=60*9.8

5. tterbecki Group Title

thanks i just thought of that lol


text:
# Whois Numbered Panda

Last week’s Intelligence blog post featured Anchor Panda, one of the many adversary groups that CrowdStrike tracks.  The adversary is the human component in an attack that one should focus on.  It is not sufficient to simply identify ‘Chinese-based hackers’; it is important to understand the adversary group that has targeted your enterprise and what intelligence they are there to collect.  By understanding that there are multiple groups and that they all have different tactics, techniques, and practices (TTPs), you can begin to understand the nature of the threat, what they are looking to collect, and raise the operational cost in order to make targeting your enterprise a costly and difficult endeavor.

Attribution is a tricky subject with regard to incident response and intrusion investigation; it can take years of research to get the home address or the location of the Technical Reconnaissance Bureau (TRB) affiliated with the threat actor.  We have to rely on the categorization of the adversary and understanding their TTPs, victims, objectives, and prior art to fully evaluate the threat that adversary poses to us.  Understanding the tasking orders the adversary has received can be revealing of the adversary, who they are working for, and their future targeting objectives. If we understand that an adversary has targeted a high-tech company’s intellectual property, then when we encounter that adversary at a different technology company, we have a pretty good idea what they are after.  Victims of a targeted attack by a “known” adversary benefit from understanding their intent in order to help gauge response and hopefully make strategic decisions about what is the appropriate countermeasure.  If the adversary is known to target mergers and acquisitions intelligence of companies involved in the Chinese market, then when that adversary shows up prior to, or during, some M&A activity, the victim can begin to take actions to limit the effectiveness of the compromised data, feed deceptive information or perhaps wage a formal complaint.  With this in mind, this week we are providing some indicators for a China based adversary who we crypt as “NUMBERED PANDA.”

Numbered Panda has a long list of high-profile victims and is known by a number of names including: DYNCALC, IXESHE, JOY RAT, APT-12, etc.  Numbered Panda has targeted a variety of victims including but not limited to media outlets, high-tech companies, and multiple governments. Numbered Panda has targeted organizations in time-sensitive operations such as the Fukushima Reactor Incident of 2011, likely filling intelligence gaps in the ground cleanup/mitigation operations.  Screen saver files, which are binary executables and PDF documents, are common Numbered Panda weaponization tactics.  One of the most interesting techniques that Numbered Panda likes to use is to dynamically calculate the Command and Control (C2) port by resolving a DNS.  This effectively helps Numbered Panda bypass egress filtering implemented to prevent unauthorized communications on some enterprises.  The malware will typically use two DNS names for communication: one is used for command and control; the other is used with an algorithm to calculate the port to communicate to.  There are several variations of the algorithm used to calculate the C2 port, but one of the most common is to multiply the first two octets of the IP address and add the third octet to that value.  This is typically represented as: (A * B) + C – common values might be 200.2.43.X, which would result in communication on port 443.  Numbered Panda will frequently use blogs or WordPress in the c2 infrastructure, which helps to make the network traffic look more legitimate.  CrowdStrike has observed Numbered Panda targeting high-tech, defense contractors, media organizations, and western governments.  The following intrusion detection rules were written and tested by the CrowdStrike Global Threat Analysis Cell (GTAC) with performance and low false positives in mind – just remember to change the Signature ID (SID) in the IDS rules.  Disclosure of this information went through the same IGL process as discussed in the Whois Anchor Panda blog post.

alert tcp $HOME_NET any ->$EXTERNAL_NET any (msg: "[CrowdStrike]
NUMBERED PANDA - Joy RAT Variant 1"; flow: from_client,established;
content: "6YmV|7c 22|"; depth: 6; sid: xxx; rev: 2; )

alert tcp $HOME_NET any ->$EXTERNAL_NET any (msg: "[CrowdStrike]
NUMBERED PANDA - Joy RAT Variant 2"; flow: from_client, established;
content: "FyojU"; depth: 6; sid: xxx; rev: 2;)

alert tcp $HOME_NET any ->$EXTERNAL_NET any  (msg: "[CrowdStrike]
NUMBERED PANDA - Joy RAT Variant 3"; flow: from_client,established;
content: "yb|13|j["; depth: 5; sid: xxx; rev: 2;)`


text:
# Electron temperature

If the velocities of a group of electrons, e.g., in a plasma, follow a Maxwell–Boltzmann distribution, then the electron temperature is defined as the temperature of that distribution. For other distributions, not assumed to be in equilibrium or have a temperature, two-thirds of the average energy is often referred to as the temperature, since for a Maxwell–Boltzmann distribution with three degrees of freedom, ${\displaystyle \langle E\rangle =(3/2)\langle k_{B}T\rangle }$.


text:
# zbMATH — the first resource for mathematics

On Hadamard groups. (English) Zbl 0906.05012
From the introduction: An Hadamard matrix $$H$$ of order $$n$$ is a $$(-1,1)$$-matrix of degree $$n$$ such that $$HH^t= nI$$, where $$t$$ denotes the transposition and $$I$$ is the identity matrix of degree $$n$$. An automorphism of $$H$$ is a pair of signed permutations $$R$$ and $$S$$ such that $$H= RHS$$, and the set of all automorphisms of $$H$$ forms a group which is called the automorphism group of $$H$$ and is denoted by $$\operatorname{Aut}(H)$$. In order to investigate the structure of $$\operatorname{Aut}(H)$$ it is convenient to regard $$H$$ as a kind of incidence matrix of a block design which is defined as follows.
Let $$D= (P, B)$$ be a block design, where $$P$$ and $$B$$ are the sets of points and blocks, respectively, satisfying the following conditions: (1) $$| P|=| B|= 2n$$, where $$| X|$$ denotes the number of elements in a finite set $$X$$. For $$\underline a\in B$$ we have that $$|\underline a|= n$$ and $$P-\underline a\in B$$. (2) For $$\underline a,\underline b\in B$$ we have that $$|\underline a\cap\underline b|= n/2$$, provided that $$\underline b\neq\underline a$$ and $$P-\underline a$$. (3) We may put $$P= \{a_1,\dots, a_n,b_1,\dots, b_n\}$$ so that $$|\underline a\cap\{a_i, b_i\}|= 1$$ for any $$\underline a\in B$$ and $$1\leq i\leq n$$. We call such a $$D$$ an Hadamard design of order $$2n$$.
Label blocks of $$B$$ so that $$B= \{\underline a_1,\dots,\underline a_n, P-\underline a_1,\dots, P-\underline a_n\}$$. Then the relation between $$D$$ and $$H$$ is as follows. $$\underline a_i$$ contains $$a_j$$ or $$b_j$$ according to whether $$H(i,j)= 1$$ or $$-1$$, where $$H(i, j)$$ is the $$(i,j)$$ component of $$H$$. It is easily seen that $$\operatorname{Aut}(H)$$ can be identified with the automorphism group $$\operatorname{Aut}(D)$$ of $$D$$ in a natural way.
From now on we consider the case where $$\operatorname{Aut}(D)$$ contains a regular subgroup which we formulate as an abstract group as follows. Let $$G$$ be a finite group of order $$2n$$. Then $$G$$ is called an Hadamard group if $$G$$ contains a subset $$D$$ with $$| D|= n$$ and an element $$e^*$$ such that (4) $$| D\cap Da|= n$$ if $$a= e$$ where $$e$$ denotes the identity element of $$G$$, $$=0$$ if $$a= e^*$$, and $$= n/2$$ for any other element $$a$$ of $$G$$, and (5) $$| Da\cap\{b, be^*\}|= 1$$ for any elements $$a$$ and $$b$$ of $$G$$.

##### MSC:
 05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.) 05B05 Combinatorial aspects of block designs 20D60 Arithmetic and combinatorial problems involving abstract finite groups
Full Text:


text:
# Algebra: lattices

1. Jan 15, 2007

### sarahr

1. The problem statement, all variables and given/known data

"Prove that in a lattice (L, <=) every finite nonempty subset S has a least upper bound and a greatest lower bound"

2. Relevant equations

3. The attempt at a solution

I'm going to try and prove this by induction.
For the initial case, show its true for n=2.
So take a lattice with 2 elts: call the elements a and b.

So then the subsets would be {a,b}, {a}, and {b} (since we don't have to deal with the nonempty). All three of these have a glb and a lub.

now assume for n. now we want to show it's true for n + 1:

this is the part im unsure about. i know its simple, but-

if it's true for n, then we just want to go once step further for n+1.
for n there are 2^n total subsets, but we are concerned about the nonempty set, so we have 2^n - 1 subsets. and all of these subsets have a glb and a lub (by assumption.)

now when we try to show this for n+1:
we have a total of 2^(n + 1) total subsets, then subtract of one for the nonempty: 2^(n + 1) - 1. the majority of these subsets overlap with the ones above in the assumption case of n, so for all of these we get for free that they have a lub and a glb. now, im not putting my finger on how many more subsets i have here in this case, and how to show that these indeed have a lub and a glb.

any suggestions?

2. Jan 16, 2007

### HallsofIvy

If $\alpha$ is the lowerbound of set A and B= A union {x}, what are the two possibilities for the lowerbound of B?

3. Jan 16, 2007

### sarahr

this is what I've got going right now:

[the previous initial step found above]

Assume it holds for all subsets of n elements, and let A = {X1, X2, ..., Xn+1}. By the induction hypothesis, {X1, X2, ..., Xn} has a lub. Call this lub L1. Since {X1, X2, ..., Xn} has a lub, then L1 union Xn+1 has a lub.

Now, I want to claim that L1 union Xn+1 is the lub of A..but how can I justify that??

And for glb, it would be the dual of the above.

?

4. Jan 16, 2007

### AKG

You need to prove it for any lattice, finite or infinite. Do induction on |S|, the size of the subset of L. Clearly, if |S| = 1, then S has a lub and a glb. Suppose that for every subset of L with size n, it has a glb and an lub. Now let S be a subset of L with |S| = n+1. Finish the proof.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook


text:
# The Problem

Suppose I have an equation of the form $\nabla^2 \phi(x) = f(x)$ on the interval $A \le x \le B$, where $f(x)$ is known and $\phi(x)$ is unknown. I have Neumann-type boundary conditions: $\frac{\partial \phi}{\partial x}\big|_{x=A} = g_A$ and $\frac{\partial \phi}{\partial x}\big|_{x=B} = g_B$, where $g_A$ and $g_B$ are known.

The compatibility constraint (derived via the divergence theorem) requires that $\int_A^B f(x) dx = g_B-g_A$. Let's assume for this problem that this is satisfied exactly such that a solution is possible.

Ultimately, I don't care about solving for $\phi$, but rather $\vec{E} = -\vec{\nabla} \phi$, but I want to use $\phi$ as the electrostatic potential because it enforces $\vec{\nabla} \times \vec{E} = 0$.

We know and expect that there is not a unique solution, but a family of solutions exist where $\phi(x) = \Phi(x) + C$, where C is any number. In other words, $\phi(x)$ is unique up to an additive constant. I don't care what this constant $C$ is, but it would be nice to be able to constrain it, and I think it is required for a numerical solution to be possible.

# Finite Difference Approach

I could set up a 2nd-order finite difference approach over $N_x$ points as follows, where $f_i \equiv f(x_i)$ and $\phi_i \equiv \phi(x_i)$:

$x_i = a + \left(\frac{b-a}{N_x-1}\right) (i-1) = a + \delta x (i-1) \qquad \text{for$i=1, 2, ...,N_x$}$,

where $\delta x \equiv \frac{b-a}{N_x-1}$.

The governing equations become $\frac{\phi_{i+1} - 2\phi_{i} + \phi_{i-1}}{\delta x^2} = f_i$.

The two boundary conditions become $\frac{\phi_2 - \phi_{0}}{\delta x} = g_A$ and $\frac{\phi_{N_x+1} - \phi_{N_x-1}}{\delta x} = g_B$.

This brings us to my issue. The PDE does not have a unique solution!

I can use ghost points ($x_0$ and $x_{N_x+1}$) and combine each boundary condition with the governing equation at each boundary. Doing so gives me $N_x$ equations and satisfies the boundary conditions. I can create a $N_x \times N_x$ matrix to solve this problem, but it is singular because $\phi(x)$ is not unique. I can add a uniqueness constraint to the matrix ($\phi_C = C$) to make a $(N_x+1) \times N_x$ matrix, but I'm afraid this will lead to a minimum-length solution.

# Concrete Example

For $N_x=7$, I have the following system of equations:

\begin{align} \phi_{2} - 2\phi_{1} + \phi_{0} \;=&\; \delta x^2 \; f_{1} \quad \text{and} \quad \phi_{2} - \phi_{0} \;=\; \delta x\; g_A \rightarrow 2 \phi_{2} - 2 \phi_{1} = \delta x g_A + \delta x^2 \; f_{1} \\ \phi_{3} - 2\phi_{2} + \phi_{1} \;=&\; \delta x^2 \; f_{2} \\ \phi_{4} - 2\phi_{3} + \phi_{2} \;=&\; \delta x^2 \; f_{3} \\ \phi_{5} - 2\phi_{4} + \phi_{3} \;=&\; \delta x^2 \; f_{4} \\ \phi_{6} - 2\phi_{5} + \phi_{4} \;=&\; \delta x^2 \; f_{5} \\ \phi_{7} - 2\phi_{6} + \phi_{5} \;=&\; \delta x^2 \; f_{6} \\ \phi_{8} - 2\phi_{7} + \phi_{6} \;=&\; \delta x^2 \; f_{7} = \quad \text{and} \quad \phi_{8} - \phi_{6} \;=\; \delta x\; g_B \rightarrow 2 \phi_{6} - 2 \phi_{7} = -\delta x \; g_B + \delta x^2 \; f_{7} \\ \end{align}

$\begin{bmatrix} -2 & 2 & 0 & 0 & 0 & 0 & 0 \\ 1 & -2 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & -2 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & -2 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & -2 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & -2 & 1 \\ 0 & 0 & 0 & 0 & 0 & 2 & -2 \end{bmatrix} \begin{bmatrix} \phi_{1} \\ \phi_{2} \\ \phi_{3} \\ \phi_{4} \\ \phi_{5} \\ \phi_{6} \\ \phi_{7} \end{bmatrix} = \begin{bmatrix} \delta x^2 \; f_{1} + \delta x \; g_A \\ \delta x^2 \; f_{2} \\ \delta x^2 \; f_{3} \\ \delta x^2 \; f_{4} \\ \delta x^2 \; f_{5} \\ \delta x^2 \; f_{6} \\ \delta x^2 \; f_{7} - \delta x; g_B \end{bmatrix}$

The problem with the above matrix equation is that it is singular. This is to be expected because $\phi$ is non-unique and is only defined up to a scalar constant.

We could specify this constant by setting the value of $\phi$ at any given point. In the above example, we could try for a unique solution by adding the constraint $\phi_4 = C$ (where $C$ is a given finite number):

$\begin{bmatrix} -2 & 2 & 0 & 0 & 0 & 0 & 0 \\ 1 & -2 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & -2 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & -2 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & -2 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & -2 & 1 \\ 0 & 0 & 0 & 0 & 0 & 2 & -2 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} \phi_{1} \\ \phi_{2} \\ \phi_{3} \\ \phi_{4} \\ \phi_{5} \\ \phi_{6} \\ \phi_{7} \end{bmatrix} = \begin{bmatrix} \delta x^2 \; f_{1} + \delta x \; g_A \\ \delta x^2 \; f_{2} \\ \delta x^2 \; f_{3} \\ \delta x^2 \; f_{4} \\ \delta x^2 \; f_{5} \\ \delta x^2 \; f_{6} \\ \delta x^2 \; f_{7} - \delta x \; g_B \\ C \end{bmatrix}$

The problem with this approach is that it is no longer a square matrix and looks like it's an over-determined system. I'm concerned that matrix-solving algorithms for non-square matrices would treat this as a least-squares problem. This isn't an over-determined system, however: the rank of the matrix equals the number of unknowns, even though the matrix isn't square.

Alternatively, I could remove one of the equations to make the matrix square.

If I were to take out the uniqueness constraint ($\phi_4 = C$), then the matrix is square but singular. (MATLAB can solve this anyway, and it gets an answer with the least error, but I don't know how it does it, and I'm concerned about it not specifying $C$.)

If I were to remove one of the governing equations ($\frac{\phi_{i+1} - 2\phi_{i} + \phi_{i-1}}{\delta x^2} = f_i$), then the system does not account for the curvature at $x=x_i$, and the solution is inaccurate.

# My Question

Is there a good algorithm for solving this type of problem, where I need more constraints than the number of unknowns, but the problem is not overdetermined?

In particular:

• Is there an algorithm that can solve the underdetermined case where $\phi_i = C$ is not included? (Is it absolutely necessary to include this constraint, or an equivalent one?)
• Is there a system of equation that is solved reliably, with minimal numerical error? I've tried rearranging the above equations and using different matrix solvers, but most of the matrices I've used give condition numbers that scale with $N_x^2$, which is concerning for the problem sizes I'm using for my research.)

A standard way how to make the solution unique is to look for the zero-mean solution $$\int_A^B\phi(x)\,\mathrm{dx}=0.$$ Let $Mu=f$ be the linear system corresponding to your finite difference approximation (with uniform discretization, constant vectors form nullspace of $M$) and $e=[1,\ldots,1]^T$. Since $M$ is symmetric and semi-definite, any solution of $Mu=f$ also minimizes $\frac{1}{2}u^TMu-u^Tf$. Imposing the zero-mean condition gives the constrained minimization problem $$\min_u \frac{1}{2}u^TMu-u^Tf\quad\text{such that}\quad e^Tu=0$$ which by introducing a Lagrange multiplier $c$ leads to a system $$\pmatrix{M&e\\e^T&0}\pmatrix{u\\c}=\pmatrix{f\\0}.$$
• So, the system should be able to be solved exactly, with zero misfit: $\left(M u_s - f\right)^T \left(M u_s - f\right) = 0$ (where $u_s$ is the calculated solution). I'm concerned that treating this as a minimization problem introduces some error. In my own tests, the Lagrange constraint is always enforced (whether $\sum_i \phi_i = 0$ or $\phi_C = C$), but the rest of the equation is not, so there is error. Mar 10 '16 at 19:47


text:
## Tuesday, May 27, 2014

### Prize season again - updated w/ Kavli winners

Once again the Breakthrough Prize and New Horizons Prize in fundamental physics are seeking nominations.  See here.  I have very mixed feelings about these prizes, given how the high energy theory components seem increasingly disconnected from experiment (and consider that a feature rather than a bug).

On a related note, the Kavli Prizes are being awarded this Thursday.  Past nanowinners are Millie Dresselhaus (2012), Don Eigler (love his current affiliation) and Nadrian Seeman (2010), and Louis Brus and Sumio Iijima (2008).   Not exactly a bunch of underachievers.  Place your bets.  Whitesides?  Alivisatos and Bawendi?

UpdateThomas Ebbeson (extraordinary transmission through deep sub-wavelength apertures, thanks to plasmons), Stefan Hell (stimulated emission depletion microscopy, for deep subwavelength fluorescence microscopy resolution), and John Pendry (perfect lenses and cloaking).  Congratulations all around - all richly deserved.  I do think that the Kavli folks are in a sweet spot for nano prizes, as there is a good-sized pool of outstanding people that has built up, few of whom have been honored already by the Nobel.  This is a bit like the early days of the Nobel prize, though hopefully with much less political infighting (see this book if you really want to be disillusioned about the Nobel process in the early years).

## Thursday, May 22, 2014

### Workshop on structural and electronic instabilities in oxide nanostructures

I've spent the last two days at a fun "Physics at the Falls" workshop at the University of Buffalo.  It's been cool learning about the impressive variety of physics at work in these systems.  A few takeaways:
• With enough stainless steel and high tech equipment you can grow (and in situ characterize with everything from electron diffraction to photoemission, angle-resolved and otherwise) just about anything these days!
• There's a lot of pretty work getting done growing epitaxial complex oxides down to the single unit cell level, and a lot of accompanying extremely high resolution transmission electron microscopy.
• Untangling thermal effects from optical effects in nonequilibrium experiments can be tricky.  Interesting to see that lower energy photons can be more efficient at kicking systems from one phase to another than photons much more energetic than any energy gap.
• There does seem to be some convergence on understanding LAO/STO oxide heterojunctions.
• We still don't understand superconductivity in strontium titanate, even though it's been known for decades.
• Orbitals really matter, when you are dealing with relatively localized electrons.
• Niagara Falls is very impressive!

## Tuesday, May 20, 2014

### Slow blogging + interesting links

The end of our academic year + travel + some major writing has cramped my blogging of late.  Things should pick back up to a more regular pace in a couple of weeks.  In the meantime, here are some links that caught my eye lately:
• On Sir Harold Kroto's website, here are some interesting lectures by Richard Feynman.  It's absolutely worth browsing around the rest of the site, too - lots of cool videos.
• This preprint by Sean Hartnoll looks very interesting.  There are materials out there that act like metals (in the sense of having lots of low energy excitations available, and an electrical resistivity that falls with decreasing temperature), but the electrons interact so strongly and in such a complex way that it no longer makes sense to think about "quasiparticles" that act basically like ordinary electrons.  The challenge is, if the quasiparticle picture (which works spectacularly well for materials like gold, copper, aluminum, doped semiconductors) fails, what's the right way to treat these systems?  This paper tries to look at what features would have to be there in such a system.
• This video is cute.  The material used in this LED has a bandgap that apparently increases a fair bit upon cooling.  As a result, the light emitted from the diode shifts toward the blue when the device is dipped in liquid nitrogen, and comes back toward the red when it's warmed.
• We still really don't understand triboelectricity, the "static electricity" you see when you rub a balloon against your hair or rub a glass rod with rabbit fur.  News story here.  It's amazing to me that we still don't know how this kind of charge transfer works, given that it was discovered thousands of years ago.  (As Pauli said, "God made the bulk; surfaces were the work of the devil.")

## Tuesday, May 06, 2014

### What are the Kramers-Kronig relations, physically?

Let me pose a puzzle.  Suppose you are in a completely dark room.  You know that at some point in the future, someone will turn on a light in that room for a few minutes, and then turn it off later.  Being a mathematically sophisticated person, it occurs to you that you could think about the time dependence of the electric field in the room.  It's zero for a while, oscillating (b/c that's what happens when there is light there) for a few minutes, and then zero again.  Being clever, you think about Fourier transforming that time dependence, and thinking about all the frequencies in there - the fact that the room right now is dark is actually because of the amazing cancellation of a whole bunch of frequency components!  Therefore, you should be able to put on glasses that are frequency-filtering, block out some of those components, and suddenly be able to see in a dark room!  Except that totally doesn't work, even in a completely classical world without photons.  Why not?

Think about a material placed in a time-varying (say, harmonically varying, because that's what physicists like) electric field.  The material responds in some way - electrons rearrange themselves within the material in response to that electric field; if the field is slow enough, atoms or groups of atoms can even shift their positions.  The result is a polarization density (electric dipole moment per unit volume) $\mathbf{P} \equiv \chi_{e}\mathbf{E}$.  Here $\chi_{e}$ is the electric susceptibility (generally a tensor, meaning that $\mathbf{P}$ and $\mathbf{E}$ don't have to point in the same direction).  The dielectric function of a material is defined $\epsilon \equiv \epsilon_{0}(1 + \chi_{e})$.  In general, the response of the material depends on the frequency $\omega$ of the electric field, and it can be out of phase with the external electric field.  This is described in mathematical shorthand by considering $\epsilon(\omega)$ to be complex, having real and imaginary components.

The Kramers-Kronig relations are fairly intimidating looking integral expressions that describe relationships that have to be obeyed between the real and imaginary components of $\epsilon(\omega)$.  These relationships come from the fact that $\mathbf{P}$ now can only depend on $\mathbf{E}$ in the past, up until now.  This restriction of causality, plus the properties of Fourier transforms, are what leads to the K-K integrals.  The wikipedia page about this actually has a very nice description here.   So, while the math is not something that most people would think of as obvious, the basic idea (electromagnetic fields influence materials in a causal way, and that places constraints on how materials can respond as a function of frequency) is not too surprising.

## Monday, May 05, 2014

### National Nano Infrastructure Network - feedback requested

I wrote before about the saga of the NNIN and how painful the outcome was this year - no awards made, after thousands of person-hours invested on the writing and reviewing of proposals.  Well, NSF is requesting input, in part because they want guidance on structuring the new solicitation to come out this autumn.  So, please give your input if you're in the US and think this kind of support for shared infrastructure is valuable.  By the way, if it seems like NSF had already gone through an exercise like this before the last solicitation (the one where they didn't fund anyone), you're right - they even had a two-day workshop and produced a report.

## Friday, May 02, 2014

### Recurring themes in (condensed matter/nano) physics: Fermi's Golden Rule

Very often in condensed matter (or atomic) physics we are interested in trying to calculate the rate of some quantum process - this could be the absorption of photons by an isolated atom or a solid, for example.  In (advanced) undergraduate quantum mechanics, we can apply time-dependent perturbation theory to do such a calculation.  Typically you assume that the system starts in some initial state $|i\rangle$, is subjected to some perturbation $V$ that turns on at time $t = 0$, and ends up in final state $|f\rangle$.  If $V$ has a harmonic time dependence with some (angular) frequency $\omega$, then you can do a nice bit of math that calculates the rate at which this process happens.  You discover that at long times the only allowed transitions are the ones where the energies of the initial and final states differ by $\hbar \omega$, and that the rate of that process is $(2\pi/\hbar) |\langle i |V| f\rangle|^{2} \rho$, where $\rho$ is the number of states per unit energy per unit volume that satisfy the energy constraint.

This result, associated with Enrico Fermi, shows up over and over, with some common motifs in condensed matter and nanoscale physics, at least in spirit (that is, sometimes people apply heuristically even though the perturbation may not be harmonic, for example).  First, the $|\langle i |V| f\rangle|^{2}$ term is what gives us selection rules.  If you think about optical transitions in atoms, this is why you get electric dipole transitions from the 2$p$ state of hydrogen to the 1$s$ state, rather than from the 2$s$ state; in the latter, this quantity is zero.  In crystalline solids, if the initial and final states are Bloch waves, it's the periodicity of the lattice that makes this quantity zero unless (crystal) momentum is conserved.  This is the root of the idea that processes ordinarily forbidden in macroscopic crystals can sometimes take place in nanocrystals or at surfaces.

Similarly, meso- and nanoscale systems can greatly constrain $\rho$.  One reason that you can get very long mean free paths for charge carriers in semiconductor nanowires, carbon nanotubes, graphene, at the edges of quantum Hall systems, etc., is that the density of states available into which carriers can scatter is very restricted.  Similarly, enhancing $\rho$ can pay dividends - this is the source of the Purcell effect, where radiative transition rates can be greatly enhanced by increasing the photon density of states, and is part of the reason for enhanced rates of optical processes near plasmonic nanostructures.


text:
# The Poincaré-Hardy Inequality on the Complement of a Cantor Set

• Cristian S. Calude
• Boris Pavlov
Conference paper
Part of the Operator Theory: Advances and Applications book series (OT, volume 134)

## Abstract

The Poincare-Hardy inequality on the complement of the Cantor set E
$$\int {\frac{{\left| u \right|^2 }}{{dist^2 \left( {x,E} \right)}}dm \leqslant 4K^2 \cdot \int {\left| {\nabla u} \right|^2 dm} }$$
holds for every u 2 1 (R 3). Corresponding higher-order inequalities will be also derived. We use a special self-similar tiling and a natural metric on the space of trajectories generated by a Mauldin-Williams graph which is homeomorphic with the space of tiles endowed with the Euclidean distance. A crude estimation of the constant K is 2,100. Three applications will be briefly discussed. In the second one, the constant 1/2K -1 ≈ 0.0002 plays the role of an estimate for the dimensionless Planck constant in the corresponding uncertainty principle.

## Keywords

Uncertainty Principle Binary String Quasiregular Mapping Minkowski Dimension Special Tiling
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

## References

1. 1.
A. Ancona. On strong barriers and an inequality of Hardy for domains in R„J. London Math. Soc.(2) 34 (1986), 274–290.
2. 2.
M.S. Birman. On spectrum of boundary value problemsMat.Sb. (N.S.)55, (1961), 125–174. (in Russian)
3. 3.
F. Bruhat and J. Tits. Groupes réductifs sur un corps localInst. Hautes Études Sci. Publ. Math.41 (1972), 5–251. (in French)
4. 4.
C. Calude.Information and RandomnessAn Algorithmic PerspectiveSpringer-Verlag, Berlin, (1994).Google Scholar
5. 5.
L. Carleson.Selected Problems on Exceptional SetsVan-Nostrand, Princeton (1967).Google Scholar
6. 6.
E.B. Davies. A review of Hardy inequalities, inThe Maz’ya Anniversary CollectionVol.2 (Rostock, 1998), 55–67,Oper. Theory Adv. Appl.110, Birkhäuser, Basel, (1999).Google Scholar
7. 7.
Gerald A. Edgar.Measure Topology and Fractal GeometrySpringer-Verlag, New York (1990).Google Scholar
8. 8.
W.N. Everitt (ed.).Inequalities: Fifty Years on from Hardy Littlewood and PolyaProceedings of the International Conference held at the University of Birmingham, Birmingham, July 13–17, 1987, Lecture Notes in Pure and Applied Mathematics, 129, Marcel Dekker, Inc., New York, (1991).Google Scholar
9. 9.
L. Carding. Dirichlet problem for linear elliptic differential equationsMath. Scand. 1(1953), 55–72.
10. 10.
G.H. Hardy, J.E. Littlewood, J.E. Polya.InequalitiesCambridge Univ. Press, Cambridge, (1934).Google Scholar
11. 11.
D.J.L. Herrmann, T. Janssen. On spectral properties of Harper-like modelsJ. Math. Physics40 3 (1999), 1197–1214.
12. 12.
P. Järvi, M. Vuorinen. Uniformly perfect sets and quasiregular mappingsJ. London Math. Soc.(2) 54 (1966), 515–529.Google Scholar
13. 13.
P. Järvi, M. Vuorinen. Self-similar Cantor sets and quasiregular mappings.J. Reine Angew. Math.424 (1992), 31–45.
14. 14.
P. Kurka. Simplicity criteria for dynamical systems, inAnalysis of Dynamical and Cognitive Systems (Stockholm 1993)189–225, Lecture Notes in Comput. Sci., 888, Springer-Verlag, Berlin, (1995).Google Scholar
15. 15.
O.A. Ladyzhenskaja.Problems in the Dynamics of Viscous Incompressible FlowGordon & Breach, New York, (1963).Google Scholar
16. 16.
D. Lind, B. Marcus. AnIntroduction to Symbolic Dynamics and CodingCambridge University Press, Cambridge, (1995).
17. 17.
V.M. Maz’ja.Sobolev SpacesSpringer-Verlag, Berlin, (1985).
18. 18.
V.L. Oleinik. Carleson measures and uniformly perfect setsZap. Nauchn. Sem. S.Peterburg. Otdel. Mat. Inst. Steklov. (POMI)255 (1998)Issled. po Linein. Oper. i Teor. Funkts.26, 92–103, 251 (in Russian).Google Scholar
19. 19.
B. Pavlov. Boundary conditions on thin manifolds and the semi-boundedness of the three-particle Schrödinger operator with pointwise potentialMath. USSR Sbornik64, 1 (1989), 161–175.
20. 20.
C.A. Pickover.Mazes for the Mind: Computers and the UnexpectedSt. Martin’s Press, New York, (1992).Google Scholar
21. 21.
Ch. Pommerenke. Uniformly perfect sets and the Poincaré metricArch. Math.32 (1979), 192–199.
22. 22.
L.I. Schiff.Quantum Mechanics3rd edition McGraw-Hill, New York, (1968).Google Scholar
23. 23.
H.G. Schuster.Deterministic ChaosPhysik-Verlag, Weiheim, (1984).Google Scholar
24. 24.
M. Reed, B. Simon.Methods of Modern Mathematical PhysicsVol. 3, Academic Press, 3rd edition, New York, (1987).Google Scholar


text:
Session 4. Galactic Center and Intermediate Mass Black Holes II
Oral, Sunday, March 23, 2003, 11:30am-12:10pm

## [4.03] A XMM-Newton and Chandra Survey of Very Low Accretion Rate AGN

A. Ptak (Johns Hopkins University), Y. Terashima (ISAS), L. C. Ho (OCIW), E. Quataert (U.C. Berkeley)

We present the results of an ongoing Chandra and XMM-Newton survey of galactic nuclei with known black hole masses and well-sampled spectral energy distributions, with emphasis here on our best-studied case, NGC 3998, a type 1'' LINER galaxy (i.e., with significant broad H\alpha emission). Our goal is to test the extent to which radiatively inefficient accretion flow (RIAF) models and/or scaled-down AGN models are consistent with the observed properties of these galaxies. We find that the XMM-Newton data, when simultaneously fitted with archival ASCA~ and BeppoSAX data, show that the 0.1--100 keV X-ray spectrum of NGC 3998 is consistent with a simple power-law model with a photon index of ~1.9. This power law also extrapolates to the UV flux determined with the OM. The upper-limit for narrow Fe-K emission is ~ 24 eV, which is one of the strictest limits to date for any AGN. This significantly rules out Fe-K emission as is expected to be observed in typical Seyfert 1 galaxies. The hard X-ray flux of NGC 3998 has not been observed to vary significantly (at >30% level) either between or within the X-ray observations, which is also in contrast to typical Seyfert 1 galaxies. The lack of any reflection features suggests that any optically thick, geometrically thin accretion disk must be truncated. RIAF models fit the optical to X-ray spectral energy distribution of NGC 3998 well. In these models the mid-IR flux also constrains the emission from any outer thin disk component that might be present. The optical to X-ray SED is also consistent with a Comptonized thin disk with a very low accretion rate (\dot{M} < 10-5\dot{M}\rm Edd). Accretion disk models in general do not account for the observed radio flux of NGC 3998. We will also present preliminary results for the other galaxies in our sample.

[Previous] | [Session 4] | [Next]

Bulletin of the American Astronomical Society, 35#2
© 2003. The American Astronomical Soceity.