1. An arithmetic processing apparatus comprising: a plurality of branch target address tables provided for respective branch instructions each having a plurality of branch targets and configured to store a history of a plurality of branch target addresses determined in a past by executing the respective branch instructions; and a branch target prediction unit configured to predict a predicted branch target address with respect to a branch instruction with reference to the history of the branch target addresses stored in a branch target address table corresponding to the branch instruction; wherein: in a first period before a branch target prediction based on a predicted branch target address predicted by the branch target prediction unit with respect to a branch instruction that completed execution is correct for first time, the branch target prediction unit sequentially registers, each time the branch instruction completes execution, a branch target address determined based on the completed branch instruction in an entry in order from a topmost entry of a branch target address table corresponding to the completed branch instruction, and outputs a branch target address registered in the topmost entry of the branch target address table corresponding to the completed branch instruction, as the predicted branch target address, and in a second period after the branch target prediction based on the predicted branch target address predicted by the branch target prediction unit with respect to the branch instruction that completed execution is correct for the first time, the branch target prediction unit sequentially selects, each time the branch instruction completes execution, an entry having a branch target address registered therein, in order from a topmost one of entries of the branch target address table corresponding to the completed branch instruction, and outputs a branch target address registered in the selected entry, as the predicted branch target address.